Algorytm Euklidesa

Algorytm Euklidesa jest szybkim sposobem obliczania największego wspólnego dzielnika dwóch (zwłaszcza dużych) liczb całkowitych.

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 + Oblicz NWD(B,R)

stosując Algorytm Euklidesa i użyj NWD(A,B) = NWD(B,R).