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