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

©2010