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.

Oblicz NWD dwóch liczb naturalnych.

,   

Zagadnienia

Liczby wzglednie pierwsze
Algorytm Euklidesa
Twierdzenia

matematyka » arytmetyka » podzielność liczb » największy wspólny dzielnik




gość logowanie

© 2014 Mariusz Śliwiński      mapa | o serwisie | kontakt | rss online: 57 drukuj