✖

Największy wspólny dzielnik

Największy wspólny dzielnik dwóch liczb całkowitych to liczba, która dzieli obie liczby bez reszty, a jednocześnie nie ma innej większej liczby, która również dzieliłaby obie liczby bez reszty.

Jako przykład rozważmy liczby 24 i 32. Jaki jest ich największy wspólny dzielnik? Przede wszystkim szukamy liczby, która dzieli obie liczby.

  • Na przykład, chociaż liczba 12 dzieli 24, nie dzieli 32, ponieważ 32 / 12 jest równa 2,666... co nie jest liczbą całkowitą. Zatem liczba 12 nie może być największym wspólnym dzielnikiem liczb 24 i 32.
  • A co z liczbą 4? Dzieli ona obie liczby, 24 / 4 jest równe 6, a 32 / 4 jest równe 8. Zatem liczba 4 jest naszym pierwszym kandydatem. Czy nie ma większej liczby, która dzieli obie liczby?
  • Liczba 8 dzieli zarówno 24, jak i 32 i jest większa od 4.
  • Nie ma liczby większej niż 8, która dzieliłaby obie liczby. Zatem liczba 8 jest największym wspólnym dzielnikiem liczb 24 i 32.

Algorytm Euklidesa do znajdowania największego wspólnego dzielnika

Istnieje stosunkowo prosty sposób na znalezienie największego wspólnego dzielnika dwóch liczb przy użyciu algorytmu Euklidesa. Zacznijmy od dwóch liczb x i y, dla których chcemy znaleźć największy wspólny dzielnik. Dla przykładu wypróbujemy to na liczbach x = 50 i y = 35 Następnie postępujemy w następujący sposób:

  1. Dzielimy x / y i zapamiętujemy resztę po dzieleniu. Zapisujemy tę resztę jako z. Dla naszego przykładu otrzymujemy 50 / 35, co daje nam resztę z = 15.
  2. Teraz zamieniamy zmienne i przechowujemy wartość y w zmiennej x i przechowujemy wartość z w y. Odrzucamy oryginalną wartość x. Po tym kroku otrzymujemy x = 35 i y = 15.
  3. Sprawdźmy teraz, czy y jest równe zero. Jeśli tak, to największym wspólnym dzielnikiem jest x. Ponieważ y nie jest równe zero, kontynuujemy i powtarzamy całą procedurę od pierwszego punktu.
  4. Ponownie dzielimy x / y, czyli dzielimy 35 / 15, co daje nam resztę po podzieleniu z = 5.
  5. Zamieniając zmienne, otrzymujemy x = 15 i y = 5. Ponieważ y nie jest równe zero, kontynuujemy.
  6. Dzielimy przez x / y, co daje 15 / 5. Reszta po dzieleniu to z = 0.
  7. Zamieniając zmienne, otrzymujemy x = 5 i y = 0.
  8. W tym momencie y = 0 to i nasz algorytm się kończy. Największym wspólnym dzielnikiem jest liczba x = 5.

Co ważne, kolejność liczb nie ma znaczenia. Gdybyśmy zamienili liczby z przykładu, otrzymalibyśmy parę x = 35 i y = 50. Procedura byłaby taka sama:

  1. Podziel x / y, a następnie podziel 35 / 50, co da nam resztę z = 35.
  2. Zamień zmienne x = 50 i y = 35.
  3. Widzimy, że po tym kroku właśnie zamieniliśmy ze sobą zawartość zmiennych x i y...

Kalkulator

Ten kalkulator obliczy największy wspólny dzielnik.