największy wspólny dzielnik adidas: Udowodnij, że NWD (n^a−1, n^{b − 1}) = n^gcd(a,b) − 1 dla n∊N⁺ oraz a,b∊N

wredulus_pospolitus: Uwielbiam to mieszanie Polskiej notacji z zagraniczną NWD(a,b) oznacza (w Polsce) dokładnie to samo (u angoli) gcm(a,b)

Adamm: NWD(n^a−1, n^b−1) = n^{max(a, b)−1} więc nie bardzo rozumiem o co biega

Adamm: n^{min(a, b)−1}

jc: Adamm, bo to powinno być chyba tak: NWD(n^a − 1, n^b − 1) = n^NWD(a,b) − 1.

jc: nwd=gcd nww=gcm

Adamm: jeśli b≥a≥0 NWD(n^a−1, n^b−1) = NWD(n^a(n^b−a−1), n^b−1) ale NWD(n^a, n^b−1) = 1, więc NWD(n^a−1, n^b−1) = NWD(n^b−a−1, n^b−1) Powtarzając proces, NWD(n^a−1, n^b−1) = NWD(n^b−k*a−1, n^b−1) gdzie 0≤b−k*a<b, k całkowite oznaczając x₁ = b, x₂ = a, x₃ = x₂−k*x₁, możemy kontynuować ten proces, do czasu gdy x_m+1 = 0 dla pewnego m, wtedy dla tego m również x_m = NWD(a, b) Zatem NWD(n^a−1, n^b−1) = NWD(0, n^{NWD(a, b)}−1) = n^{NWD(a, b)}−1

Adamm: po prostu trzeba zauważyć że dostajemy algorytm Euklidesa w potęgach