największy wspólny dzielnik adidas: Udowodnij, że NWD (na−1, nb − 1) = ngcd(a,b) − 1 dla n∊N+ oraz a,b∊N
12 mar 11:42
wredulus_pospolitus: Uwielbiam to mieszanie Polskiej notacji z zagraniczną NWD(a,b) oznacza (w Polsce) dokładnie to samo (u angoli) gcm(a,b)
12 mar 12:07
Adamm: NWD(na−1, nb−1) = nmax(a, b)−1 więc nie bardzo rozumiem o co biega
12 mar 12:29
Adamm: nmin(a, b)−1
12 mar 12:29
jc: Adamm, bo to powinno być chyba tak: NWD(na − 1, nb − 1) = nNWD(a,b) − 1.
12 mar 12:42
jc: nwd=gcd nww=gcm
12 mar 12:43
Adamm: jeśli b≥a≥0 NWD(na−1, nb−1) = NWD(na(nb−a−1), nb−1) ale NWD(na, nb−1) = 1, więc NWD(na−1, nb−1) = NWD(nb−a−1, nb−1) Powtarzając proces, NWD(na−1, nb−1) = NWD(nb−k*a−1, nb−1) gdzie 0≤b−k*a<b, k całkowite oznaczając x1 = b, x2 = a, x3 = x2−k*x1, możemy kontynuować ten proces, do czasu gdy xm+1 = 0 dla pewnego m, wtedy dla tego m również xm = NWD(a, b) Zatem NWD(na−1, nb−1) = NWD(0, nNWD(a, b)−1) = nNWD(a, b)−1
12 mar 12:45
Adamm: po prostu trzeba zauważyć że dostajemy algorytm Euklidesa w potęgach
12 mar 12:47