Przypomnijmy, że Największy Wspólny Dzielnik (NWD) dwu liczb całkowitych A i B jest największą liczbą całkowitą, która dzieli A oraz B.
Algorytm Euklidesa pozwala na szybkie znalezienie NWD dwóch liczb całkowitych.

Algorytm

Algorytm Euklidesa znajdujący NWD(A,B) wygląda tak:
  • Jeśli A = 0, to NWD(A,B)=B (gdyż NWD(0,B)=B) i możemy się zatrzymać.  
  • Jeśli B = 0, to NWD(A,B)=A (gdyż NWD(A,0)=0) i możemy się zatrzymać.  
  • Wykonaj dzielenie z resztą A = B⋅Q + R
  • Oblicz NWD(B,R) stosując Algorytm Euklidesa i użyj NWD(A,B) = NWD(B,R).

Przykład:

Znajdź NWD liczb 270 i 192:
  • A=270, B=192
  • A ≠0
  • B ≠0
  • Używając dzielenia pod kreską mamy 270/192 = 1 z resztą 78. Możemy to zapisać jako 270 = 192 * 1 + 78
  • Obliczamy NWD(192,78), by użyć NWD(270,192)=NWD(192,78)
A=192, B=78
  • A ≠0
  • B ≠0
  • Używając dzielenia pod kreską mamy 192/78 = 2 z resztą 36. Możemy to zapisać jako:
  • 192 = 78 * 2 + 36
  • Obliczamy NWD(78,36), by użyć NWD(192,78)=NWD(78,36)
A=78, B=36
  • A ≠0
  • B ≠0
  • Używając dzielenia pod kreską mamy 78/36 = 2 z resztą 6. Możemy to zapisać jako:
  • 78 = 36 * 2 + 6
  • Obliczamy NWD(36,6), by użyć NWD(78,36)=NWD(36,6)
A=36, B=6
  • A ≠0
  • B ≠0
  • Używając dzielenia pod kreską mamy 36/6 = 6 z resztą 0. Możemy to zapisać jako:
  • 36 = 6 * 6 + 0
  • Obliczamy NWD(6,0), by użyć NWD(36,6)=NWD(6,0)
A=6, B=0
  • A ≠0
  • B =0, NWD(6,0)=6
Pokazaliśmy więc:
NWD(270,192) = NWD(192,78) = NWD(78,36) = NWD(36,6) = NWD(6,0) = 6
NWD(270,192) = 6

Zastanówmy się, dlaczego Algorytm Euklidesa działa

Przyglądając się uważnie algorytmowi Euklidesa, widzimy, że korzysta z następujących własności:
  • NWD(A,0) = A
  • NWD(0,B) = B
  • Jeśli A = B⋅Q + R i B≠0, to NWD(A,B) = NWD(B,R), gdzie Q jest liczbą całkowitą, a R liczbą całkowitą w przedziale od 0 do B-1
Dwie pierwsze własności wyznaczają NWD dwu liczb, gdy jedną z nich jest zero. Trzecia pozwala nam sprowadzić problem większy, bardziej skomplikowany, do mniejszego, łatwiejszego do rozwiązania.
Algorytm Euklidesa wykorzystuje trzecią własność, krok po kroku sprowadzając zadanie do coraz prostszych przypadków, aż wreszcie uda się je rozwiązać dzięki dwu pierwszym własnościom.
By zrozumieć te trzy własności, dowiedziemy ich.
Możemy udowodnić, że NWD(A,0)=A następująco:
  • Największą liczbą całkowitą, która dzieli A jest A.
  • Każda liczba całkowita dzieli 0, gdyż dla każdej liczby całkowitej C mamy C⋅0 = 0. Zatem A dzieli 0.
  • Największą liczbą, która dzieli A oraz 0 jest A.
Własności NWD(0,B)=B dowodzimy podobnie (jak wyżej, tylko z B w miejscu A).
By udowodnić NWD(A,B)=NWD(B,R), pokażemy wpierw, że NWD(A,B)=NWD(B,A-B).
Niech A,B i C będą trzema liczbami całkowitymi takimi, że A-B=C.
Pokazujemy, że NWD(A,B) dzieli C
NWD(A,B) dzieli A z definicji. Stąd A musi być wielokrotnością NWD(A,B), tj. X⋅NWD(A,B)=A, gdzie X jest pewną liczbą całkowitą
NWD(A,B) dzieli B z definicji. Stąd B musi być wielokrotnością NWD(A,B), tj. Y⋅NWD(A,B)=B, gdzie Y jest pewną liczbą całkowitą
A-B=C daje:
  • X⋅NWD(A,B) - Y⋅NWD(A,B) = C
  • (X - Y)⋅NWD(A,B) = C
Widzimy zatem, że NWD(A,B) dzieli C.
Tę część dowodu zilustrowano poniżej:
Dowód, że NWD(B,C) jest dzielnikiem A
NWD(B,C) dzieli B z definicji. Stąd B musi być wielokrotnością NWD(B,C), tj. M⋅NWD(B,C)=B, gdzie M jest pewną liczbą całkowitą
NWD(B,C) dzieli C z definicji. Stąd C musi być pewną wielokrotnością NWD(B,C), tj. N⋅NWD(B,C)=C, gdzie N jest pewną liczbą całkowitą
A-B=C daje:
  • B+C=A
  • M⋅NWD(B,C) + N⋅NWD(B,C) = A
  • (M + N)⋅NWD(B,C) = A
Widzimy zatem, że NWD(B,C) dzieli A.
Tę część dowodu zilustrowano poniżej
Dowód, że GCD(A,B)=GCD(A,A-B)
  • NWD(A,B) dzieli B z definicji.
  • Pokazaliśmy, że NWD(A,B) dzieli C.
  • Skoro NWD(A,B) dzieli zarówno B, jak i C, jest wspólnym dzielnikiem B i C.
NWD(A,B) jest mniejszy, bądź równy NWD(B,C), ponieważ NWD(B,C) jest największym wspólnym dzielnikiem B i C.
  • NWD(B,C) dzieli B z definicji.
  • Pokazaliśmy, że NWD(B,C) dzieli A.
  • Skoro NWD(B,C) dzieli zarówno A, jak i B, jest wspólnym dzielnikiem A i B.
NWD(B,C) jest mniejszy, bądź równy NWD(A,B), ponieważ NWD(A,B) jest największym wspólnym dzielnikiem A i B.
Mając NWD(A,B)≤NWD(B,C) i NWD(B,C)≤NWD(A,B) stwierdzamy, że:
NWD(A,B)=NWD(B,C)
Co jest równoważne:
NWD(A,B)=NWD(B,A-B)
Dowód ten zilustrowano w prawej części poniższego rysunku.
Dowód, że NWD(A,B)=NWD(B,R)
Pokazaliśmy, że NWD(A,B)=NWD(B,A-B)
Kolejność argumentów nie ma znaczenia, więc możemy napisać NWD(A,B)=NWD(A-B,B)
Możemy wielokrotnie użyć tożsamości NWD(A,B)=NWD(A-B,B), dostając:
NWD(A,B)=NWD(A-B,B)=NWD(A-2B,B)=NWD(A-3B,B)=...=NWD(A-Q⋅B,B)
Ale A= B⋅Q + R, więc  A-Q⋅B=R
Zatem NWD(A,B)=NWD(R,B)
Kolejność argumentów nie ma znaczenia, więc
NWD(A,B)=NWD(B,R)
Ładowanie