Największy wspólny dzielnik
Jeżeli liczba $d$ dzieli liczbę $a$ bez reszty, to mówimy, że liczba $d$ jest dzielnikiem liczby $a$. Każda liczba większa od $1$ ma co najmniej dwa dzielniki: $1$ i samą siebie, ponieważ liczba $1$ jest dzielnikiem każdej liczby oraz każda liczba różna od zera jest swoim dzielnikiem.
Jeśli liczba $d$ jest dzielnikiem liczby $a$, ale także dzielnikiem liczby $b$, to $d$ jest wspólnym dzielnikiem liczb $a$ i $b$.
Największy wspólny dzielnik dwóch liczb całkowitych $a$ i $b$, z których co najmniej 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)$ lub NWD$(a, b)$ lub po prostu $(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 największego wspólnego dzielnika dwóch liczb. Jedna z nich to szukanie takiego dzielnika w pamięci, jednak metoda ta jest mało przydatna dla dużych liczb z oczywistych względów. Można skorzystać z metody, w której każdą z liczb należy rozłożyć na czynniki pierwsze, gdzie iloczyn wspólnych czynników równy jest największemu wspólnemu dzielnikowi. Tu jednak kłopotem może być rozkład na czynniki pierwsze dużych liczb. Z pomocą przychodzą nam komputery, które z roku na rok mają coraz większą moc obliczeniową.
Przykład
nwd$(36, 48) = ?$
$36 = 2 \cdot 2 \cdot 3 \cdot 3$
$48 = 2 \cdot 2 \cdot 2 \cdot 2 \cdot 3$
wspólne czynniki: $2, 2, 3$
nwd$(36, 48) = 2 \cdot 2 \cdot 3 = 12$