Największy wspólny dzielnik

Wyjaśnienie problemu

Największy wspólny dzielnik (NWD) dwóch liczb całkowitych – to największa liczba naturalna, która dzieli obie te liczby bez reszty.

Zatem metoda pierwsza

Największy wspólny dzielnik (NWD) znajduje się następująco. Rozkładem liczby na czynniki pierwsze, zakreślam wspólne dzielniki, mnożę zakreślone dzielniki i tak otrzymujemy liczbę będącą NWD.

Przykład

NWD(280,150) = 2 * 5 = 10

NWD(36,16) = 2 * 2 = 4

Zatem metoda druga

Algorytm Euklidesa jest szybkim sposobem obliczania największego wspólnego dzielnika dwóch (zwłaszcza dużych) liczb całkowitych. Polega ona na dzieleniu modulo (reszta z dzielenie).

Algorytm

Aby obliczyć NWD(a,b), wykonujemy kolejno następujące kroki:

1. Dzielimy z resztą liczbę a przez liczbę b
   • jeżeli reszta =0, to NWD(a,b)=b
   • jeżeli reszta ?0, to przypisujemy liczbie a wartość liczby b, liczbie b wartość otrzymanej reszty, a następnie wykonujemy ponownie punkt 1.

Przykład

Liczba A = 280  B = 150

280 : 150 = 1 reszty 130
150 : 130 = 1 reszty 20
130 : 20 = 6 reszty 10
20 : 10 = 2 reszty 0

Otrzymaliśmy resztę równą zero, zatem szukany NWD będzie równy ostatniej niezerowej reszcie:

NWD(280, 150) = 10

Zatem metoda trzecia

Największy wspólny dzielnik (NWD) możemy wyznaczyć metodą Euklidesa, która polega na wyznaczeniu dwóch liczb naturalnych. Kolejnym krokiem jest sprawdzenie, która liczba jest większa i zamianie miejscami jeśli to konieczne, aby ustawić większa liczba na początku. Następnie wykonujemy odejmowanie, powstały wynik podstawiamy pod liczbę większą, gdzie powstaje nowa para. Powtarzamy te czynności do momentu, kiedy dwie liczby są równe.

Przykład

Liczba A = 280 B = 150

280 – 150 = 130
150 – 130= 20
130 – 20 = 110
110 – 20 = 90
90 – 20 = 70
70 – 20 = 50
50 -20 = 30
30 – 20 = 10
20 – 10 = 10
10 10

Ponieważ liczby są sobie równe, oznacza to, że największy wspólny dzielnik liczb 280 i 150 to 10.