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 ma co najmniej 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 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).
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 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.
Zagadnienia
