Największy wspólny dzielnik
Z Wikipedii
Największym wspólnym dzielnikiem dwóch lub więcej liczb naturalnych dodatnich a1, a2,... , an nazywamy największą liczbę naturalną, która jest jednocześnie dzielnikiem każdej z liczb a1,... an.
Największy wspólny dzielnik oznacza się często symbolem NWD(a1...an), a w literaturze angielskiej GCD (z ang. greatest common divisor).
Zmiana kolejności argumentów NWD nie zmienia jego wartości. Zachodzi: 
Zachodzi również zależność:
Dla dwóch liczb zachodzi też zależność:
gdzie NWW to najmniejsza wspólna wielokrotność. Dla więcej niż dwóch liczb zależność taka nie jest prawdziwa.
Jeśli NWD(a1...an)=1, to liczby a1...an nazywamy względnie pierwszymi.
Istotnym faktem w algebrze jest także możliwość przedstawienia NWD( a1,... an ) jako liniowego zlożenia liczb a1 do an, tj. dla każdej n-tki A = <a1, ..., an> liczb naturalnych istnieje n-tka liczb całkowitych K = <k1, ..., kn> taka, że zachodzi: NWD( A ) = k1 * a1 + ... + kn * an .
W szczególności dla liczb wzglednie pierwszych mamy: 1 = NWD( A ) = k1 * a1 + ... + kn * an, dla pewnej n-tki K.
Znanym algorytmem znajdowania największego wspólnego dzielnika dwóch liczb jest algorytm Euklidesa.
