Największy wspólny dzielnik
Jeżeli d|a, to mówimy, że liczba d jest dzielnikiem liczby a. Każda liczba ma conajmniej dwa dzielniki: 1 i samą siebie (wyjątkiem jest oczywiście liczba 1), ponieważ liczba 1 jest dzielnikiem każdej liczby, oraz każda liczba różna od zera jest swoim dzielnikiem.
Jeśli teraz liczba d jest dzielnikiem liczby a, ale także dzielnikiem liczby b, to d jest wspólnym dzielnikiem liczb a i b. Należy zauważyć, że liczba 1 jest dzielnikiem dowolnych dwóch liczb całkowitych.
Największy wspólny dzielnik dwóch liczb całkowitych a i b, z których co naj mniej jedna jest różna od zera, to największy spośród wspólnych dzielników liczb a i b.
Największy wspólny dzielnik liczb a i b zapisujemy
NWD(a, b).
Jeśli największy wspólny dzielnik dwóch liczb jest równy 1, to liczby
takie nazywamy względnie pierwsze.
Jest klika metod na odnajdywanie NWD dwóch liczb. Jedna z nich to szukanie takiego dzielnika w pamięci, jednak metoda ta jest mało przydatna z oczywistych względów. Można skożystać z metody, w której każdą z liczb należy rozłożyć na czynniki pierwsze, gdzie iloczyn jednakowych czynników równy jest największemu wspólnemu dzielnikowi. Tu jednak kłopotem może być rozkład na czynniki pierwsze.