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$


Oblicz nwd dwóch liczb naturalnych.

,   

Test - nwd i nww (SP)


Twierdzenia

matematyka » arytmetyka » podzielność liczb » dzielniki i wielokrotności » największy wspólny dzielnik




gość logowanie

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