Największy wspólny dzielnik
Największy wspólny dzielnik (NWD) dwóch liczb całkowitych to taka liczba, która dzieli obie liczby bez reszty, a przy tym nie istnieje żadna inna, większa liczba, która też dzieliłaby obie liczby bez reszty.
Weźmy dla przykładu liczby 24 i 32. Ile wynosi ich największy wspólny dzielnik? Szukamy przede wszystkim liczby, która dzieli obie liczby.
- Na przykład liczba 12 wprawdzie dzieli liczbę 24, ale nie dzieli liczby 32, bo 32 / 12 jest równe 2,666…, a to nie jest liczba całkowita. Liczba 12 nie może więc być największym wspólnym dzielnikiem liczb 24 i 32.
- A może liczba 4? Ta dzieli obie liczby, 24 / 4 jest równe 6, a 32 / 4 jest równe 8. Liczba 4 jest więc naszym pierwszym kandydatem. Czy nie istnieje jakaś większa liczba, która dzieliłaby obie liczby?
- Liczba 8 dzieli zarówno liczbę 24, jak i liczbę 32, a przy tym jest większa od liczby 4.
- Nie istnieje żadna inna liczba większa od 8, która dzieliłaby obie liczby. Liczba 8 jest więc największym wspólnym dzielnikiem liczb 24 i 32.
Algorytm Euklidesa do wyznaczania największego wspólnego dzielnika
Istnieje dość prosty sposób, jak znaleźć największy wspólny dzielnik dwóch liczb – algorytm Euklidesa. Na początku mamy dwie liczby x i y, dla których chcemy znaleźć największy wspólny dzielnik. Wypróbujemy to na liczbach x = 50 i y = 35. Postępujemy tak:
- Dzielimy x / y i zapamiętujemy resztę z dzielenia. Tę resztę oznaczymy jako z. W naszym przykładzie dzielimy 50 / 35, co daje resztę z = 15.
- Teraz przesuwamy wartości: do zmiennej x wpisujemy wartość y, a do y wartość z. Pierwotną wartość x wyrzucamy. Po tym kroku mamy x = 35 i y = 15.
- Teraz sprawdzamy, czy y jest równe zeru. Jeśli tak, największym wspólnym dzielnikiem jest liczba x. Ponieważ y nie jest równe zeru, idziemy dalej i powtarzamy całą procedurę od pierwszego punktu.
- Znowu dzielimy x / y, czyli 35 / 15, co daje resztę z dzielenia z = 5.
- Przesuwamy wartości, dostajemy więc x = 15 i y = 5. Ponieważ y nie jest równe zeru, idziemy dalej.
- Dzielimy x / y, czyli 15 / 5. Reszta z dzielenia wynosi z = 0.
- Przesuwamy wartości i dostajemy x = 5 i y = 0.
- W tej chwili y = 0 i nasz algorytm się kończy. Największym wspólnym dzielnikiem jest liczba x = 5.
Ważne jest, że kolejność liczb nie ma znaczenia. Gdybyśmy zamienili liczby z przykładu, dostalibyśmy parę x = 35 i y = 50. Postępowanie byłoby takie samo:
- Dzielimy x / y, czyli 35 / 50, co daje resztę z = 35.
- Przesuwamy wartości: x = 50 i y = 35.
- Widzimy, że po tym kroku po prostu zamieniliśmy ze sobą zawartość zmiennych x i y…