|
Brojevi su [i]x[/i] i [i]y[/i] i vrijedi: [i]x[/i] = [i]am[/i], [i]y[/i] = [i]bm[/i], gdje je [i]m[/i] = M([i]x[/i], [i]y[/i]), tj. M([i]a[/i], [i]b[/i]) = 1. :)
BSOMP: [i]x[/i] > [i]y[/i]
Vrijedi: [i]x[/i] = [i]ky[/i] + [i]x[/i]', gdje je 0 <= [i]x[/i]' < [i]y[/i]
Uvrsti [i]x[/i] i [i]y[/i] i baci ih na istu stranu:
[i]x[/i]' = [i]am[/i] - [i]kbm[/i] = [i]m[/i]([i]a[/i] - [i]kb[/i]),
sto znaci da je i [i]x[/i]' djeljiv s [i]m[/i]. 8) Kako je [i]x[/i]' < [i]x[/i], ovako dobiveni niz [i]x[/i]-eva strogo pada, pa moramo doci do najmanjeg djeljivog s [i]m[/i], a to je upravo sam [i]m[/i] (iduci je nula i to dobijes u koraku nakon sto dobijes [i]m[/i]).
HTH 8)
P.S. Bilo bi ispravnije raspisati po koracima, s indeksima - npr. nizovi [latex]x_i, y_i[/latex] - ali mi se to nije dalo; vjerujem da ti je ideja dosta. ;)
Brojevi su x i y i vrijedi: x = am, y = bm, gdje je m = M(x, y), tj. M(a, b) = 1. 
BSOMP: x > y
Vrijedi: x = ky + x', gdje je 0 ⇐ x' < y
Uvrsti x i y i baci ih na istu stranu:
x' = am - kbm = m(a - kb),
sto znaci da je i x' djeljiv s m.  Kako je x' < x, ovako dobiveni niz x-eva strogo pada, pa moramo doci do najmanjeg djeljivog s m, a to je upravo sam m (iduci je nula i to dobijes u koraku nakon sto dobijes m).
HTH
P.S. Bilo bi ispravnije raspisati po koracima, s indeksima - npr. nizovi  - ali mi se to nije dalo; vjerujem da ti je ideja dosta. 
_________________ U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.  |
