Algorytm Euklidesa

Algorytm Euklidesa

Tw. o dzieleniu z resztą
Przykład
\(a=26, b=11\). Wtedy stwierdzamy, że \(q=2\) oraz \(r=4\), bo
\(26=2 \cdot 11 + 4\)
Uwaga
Przykłady
\(12\mid 24\), bo \(24=2\cdot 12+0\) (czytamy 12 dzieli 24)
\(2\mid 4\), bo \(4=2\cdot 2+0\) (czytamy 2 dzieli 4)
ale \(3\not\mid 5\), bo \(5=2\cdot 2 +1\) (czytamy 3 nie dzieli 5)

Algorytm Euklidesa

Dla dowolnych liczb całkowitych \(a\) i \(b\) na mocy Tw. o dzieleniu z resztą mamy
$$a=q_{1}b+r_{1}, 0< r_{1}< |b|$$ $$b=q_{2}r_{1}+r_{2}, 0< r_{2}< |r_{1}|$$ $$r_{1}= q_{3}r_{2} +r_{3}, 0< r_{3}< |r_{2}|$$ $$\vdots$$ $$r_{n-2}= q_{n}r_{n-1}+r_{n}, 0< r_{n} < |r_{n-1}|$$ $$r_{n-1}= q_{n+1}r_{n}$$ Wówczas \(r_{n}=NWD(a, b)\) (ostatnia niezerowa reszta).
Dowód
oznaczmy \(d = NWD(a, b)\)
Algorytm zawsze się zatrzymuje, bo w każdym kroku otrzymujemy liczbę (resztę) co najmniej o 1 mniejszą od poprzednej, więc kiedyś dojdziemy do zera. Z ostatniej równości $$r_{n-1}= q_{n+1}r_{n}$$ widzimy, że \(r_{n}\mid r_{n-1}\). Z pozostałych równości wynika \(r_{n} \mid r_{n-2}, …, r_{n} \mid r_{1}\) zatem
\(r_{n} \mid a, r_{n} \mid b\) (ostatnia niezerowa reszta jest wspólnym dzielnikiem liczb \(a\) i \(b)\) , a więc w szczególności \(r_{n}\mid d\).
Z drugiej strony \(d \mid a\) i \(d \mid b\), a więc patrząc na pierwszą równość \(a=q_{1}b+r_{1}\) stwierdzamy, że \(d \mid r_{1}\). Dalej kolejno \(d \mid r_{2}, …, d \mid r_{n-1}, d \mid r_{n}\).
Ponieważ \(r_{n} \mid d\) i jednocześnie \(d \mid r_{n}\), więc \(d = r_{n}\). Zaletą algorytmu Euklidesa jest to, że nie musimy liczby rozkładać na czynniki pierwsze, aby obliczyć ich NWD. Przykład
powrót do spisu