Question

Co to jest algorytm Euklidesa i jakie ma zastosowanie?

Answer 1

Algorytm Euklidesa służy do wyznaczenia największego wspólnego dzielnika NWD. Zastosowanie to skracanie ułamków zwykłych, do postaci najprostrzej, tzw. ułamka właściwego, tzn. takiego, którego nie można już dalej uprościć. Oznaczamy go np NWD(30,18)=6.
NWD Największy Wspólny Dzielnik dwóch liczb jest największą liczbą naturalną spośród tych, które dzielą obie te liczby bez reszty.

Znajdowanie NWD przy pomocy algorytmu Euklidesa :
1. Wprowadź dwie liczby naturalne a i b
2. Oblicz c jako resztę z dzielenia a przez b
3. Zastąp a przez b, zaś b przez c
4. Jeżeli b=0, to szukane NWD=a, w przeciwnym wypadku wróć do punktu drugiego i kontynuuj.

przykład 1. liczby 30 i 18
30:18=1, reszty 12
18:12=1, reszty 6
12:6=2, reszty 0
NWD(30,18)=6

przykład 2. liczby 77 i 53
77:53=1, reszty 24
53:24=2, reszty 5
24:5=4, reszty 4
5:4=1, reszty 1
4:1=4, reszty 0
NWD(77,53) = 1
Liczby 77 i 53 są względnie pierwsze.

przykład 3: 126 i 36
126:36=3, reszty 18
36:18=2, reszty 0
NWD(126,36)=18

przykład 4: 756 i 41
756:41=18, reszty 18
41:18=2, reszty 5
18:5=3, reszty 3
5:3=1, reszty 2
3:2=1, reszty 1
2:1=2, reszty 0
NWD(756,41)=1
Liczby 756 i 41 są względnie pierwsze.