Co to jest największy wspólny dzielnik - NWD?
Jeżeli dwie liczby, z których przynajmniej jedna jest różna od zera, mają wspólne dzielniki, to największy spośród tych dzielników to ich największy wspólny dzielnik, który oznaczamy jako NWD.
Algorytm znajdywania NWD:
Metoda 1:
Jeżeli mamy znaleźć NWD liczb i
, to najpierw te liczby rozkładamy na czynniki pierwsze. Wypisujemy te czynniki, które powtórzyły się w obu rozkładach (każdy czynnik tylko raz). Następnie mnożymy je przez siebie i w ten sposób otrzymujemy największy wspólny dzielnik. Zobacz przykład poniżej.
Rozkładamy liczby i
na czynniki pierwsze:
Szukamy czynników, które występują w obu rozkładach jednocześnie:
Mnożymy te czynniki prze siebie, otrzymując największy wspólny dzielnik:
Inna metoda znajdowania NWD została opracowana przez Euklidesa jeszcze w starożytności. Jest to tzw Algorytm Euklidesa, który jest bardzo skuteczny w przypadku znajdowania NWD dużych liczb.
Zobacz rozwiązanieNajwiększy wspólny dzielnik pewnych liczb
i
wynosi
, natomiast ich najmniejsza wspólna wielokrotność wynosi
. Znajdź liczby
i
, jeżeli wiadomo, że obie te liczby są mniejsze od
.
Zobacz rozwiązanieLiczby
i
podzielono przez pewną liczbę. Przy dzieleniu
przez tą liczbę otrzymano resztę
, natomiast przy dzieleniu
otrzymano resztę
. Jaka to liczba?
Zobacz rozwiązanieWykaż, że
,
dla pewnych liczb naturalnych
.
Przeczytaj także:
COMMENT_CONTENT