Co to jest Algorytm Euklidesa
Algorytm Euklidesa to alternatywny schemat znajdowania NWD dla dwóch liczb.
Euklidesa opisał to następująco:
Jeżeli szukamy , gdzie
oraz
to postępujemy następująco:
Dzielimy liczbę przez
. Otrzymujemy liczbę
oraz resztę z dzielenia
.
Dzielimy liczbę przez
. Otrzymujemy liczbę
oraz resztę z dzielenia
.
Ten algorytm powtarzamy, aż do momentu, gdy reszta z dzielenie będzie zerem. Wtedy największym wspólnym dzielnikiem jest ostatnia niezerowa reszta.
Przykład 1
Zgodnie z opisem powyżej, dzielimy przez
:
Zatem są to liczby względnie pierwsze.
Brak komentarzy
Dodaj komentarz
Musisz się
zalogować
aby dodać komentarz
COMMENT_CONTENT