[Teoria liczb] NWD dwóch liczb

[laurelandilas]

Wyznacz największy wspólny dzielnik liczb:
\(\displaystyle{ 2 ^{37} - 1}\) i \(\displaystyle{ 2 ^{19} - 1}\)

[Citizen]

Dość znany jest fakt:
\(\displaystyle{ NWD(2^{n}-1,2^{m}-1)=2^{NWD(n,m)}-1}\)
\(\displaystyle{ n,m \in N}\)

[laurelandilas]

A gdzie moge znalezc dowod tego twierdzenia?

[Citizen]

Tego nie wiem, ale jeżeli \(\displaystyle{ n,m}\) są liczbami pierwszymi (tak jak w twoim zadaniu) to dowód, że \(\displaystyle{ NWD(2^{n}-1,2^{m}-1)=1}\) masz w rozwiązaniu zadania 10 z pierwszego etapu tegorocznego OM ... adania.php

[tkrass]

No bez żartów, dowód tego faktu to pałkerskie nawalanie Euklidesem.

[ordyh]

Najpierw lemat:
Jeżeli \(\displaystyle{ (x,y) = 1}\), to \(\displaystyle{ (a^x-1,a^y-1) = a-1}\).
Niech \(\displaystyle{ d = (a^x-1,a^y-1)}\). Mamy \(\displaystyle{ a^x \equiv 1 \pmod d}\), \(\displaystyle{ a^y \equiv 1 \pmod d}\). Niech \(\displaystyle{ t = ord_d a}\), mamy, że \(\displaystyle{ t|x}\) i \(\displaystyle{ t|y}\), więc \(\displaystyle{ t=1}\), zatem \(\displaystyle{ d|a-1}\). Zauważmy, że \(\displaystyle{ a-1|a^x-1}\) i \(\displaystyle{ a-1|a^y-1}\), zatem \(\displaystyle{ d = a-1}\).

Teraz udowodnimy, że \(\displaystyle{ (a^x-1,a^y-1) = a^{(x,y)}-1}\). Niech \(\displaystyle{ d = (x,y)}\) i \(\displaystyle{ x = kd}\), \(\displaystyle{ y=ld}\), \(\displaystyle{ (k,l)=1}\). Stąd na podstawie lematu wyżej \(\displaystyle{ (a^x-1,a^y-1) = ((a^d)^k-1,(a^d)^l-1) = a^d-1 = a^{(x,y)}-1}\) ckd.

[Swistak]

No bez żartów, dowód tego faktu to pałkerskie nawalanie Euklidesem.

Ja się nie zgodzę (co do tego, że to pałkerskie), wg mnie dowód tego faktu jest całkiem trikowy.