1. Algorytm Euklidesa
Drukuj

Co to jest największy wspólny dzielnik - NWD?

Definicja: Największy wspólny dzielnik

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 a i b, 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.

Przykład 8

NWD(36,45)=?

Rozkładamy liczby 36 i 45 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:

NWD(36,45)=3 * 3=9

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.


Zadanie 1
Premium

Największy wspólny dzielnik pewnych liczb a i b wynosi 2, natomiast ich najmniejsza wspólna wielokrotność wynosi 84. Znajdź liczby a i b, jeżeli wiadomo, że obie te liczby są mniejsze od 20.

Zobacz rozwiązanie
  • Matura rozszerzona
  • 38 komentarzy

Zadanie 2
Premium

Liczby 54 i 38 podzielono przez pewną liczbę. Przy dzieleniu 54 przez tą liczbę otrzymano resztę 9, natomiast przy dzieleniu  38 otrzymano resztę 8 . Jaka to liczba?

Zobacz rozwiązanie
  • Matura rozszerzona
  • 9 komentarzy

Zadanie 3

Wykaż, że

a* b=NWD(a,b)* NWW(a,b),

dla pewnych liczb naturalnych a,\ b.

Zobacz rozwiązanie
  • Matura rozszerzona
  • 37 komentarzy

Przeczytaj także:

Brak komentarzy

Dodaj komentarz

Musisz się zalogować aby dodać komentarz