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.

Oblicz NWD dowolnych dwóch liczb naturalnych. (1 < a, b < 10000)

,   

Zagadnienia

Liczby wzglednie pierwsze
Algorytm Euklidesa
Twierdzenia

narzędzia słownik wzory tablice
matematyka » arytmetyka » podzielność liczb » największy wspólny dzielnik

Copyright © 2008 Mariusz Śliwiński

Osób online: 33

Drukuj