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 NWD(a,b), gdzie a>b oraz b\neq 0 to postępujemy następująco:

Dzielimy liczbę a przez b. Otrzymujemy liczbę c_1 oraz resztę z dzielenia r_1.

Dzielimy liczbę b przez r_1. Otrzymujemy liczbę c_2 oraz resztę z dzielenia r_2.

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

NWD(59,34)

Zgodnie z opisem powyżej, dzielimy 59 przez 34:

59:34=1 \ \text{reszty}\ 25

34:25=1 \ \text{reszty}\ 9

25:9=2 \ \text{reszty}\ 7

9:7=1 \ \text{reszty}\ 2

7:2=3 \ \text{reszty}\ \boxed{1}

2:1=2\ \ \text{reszty}\ 0

NWD(59,34)=1

Zatem są to liczby względnie pierwsze.

Brak komentarzy

Dodaj komentarz

Musisz się zalogować aby dodać komentarz