Rozszerzony algorytm Eukliedesa
Liczby wygenerowane przez algorytm Euklidesa pozwalaj± wyznaczyć liczby całkowite $x, y$ takie, że
$$ax+by=NWD(a, b)$$
Przykład
Rozwi±zać w liczbach całkowitych równanie
$$48x+62y = NWD(48, 62)$$
Obliczamy NWD(48, 62) korzystaj±c z algorytmu Euklidesa
$$62 = 14 +1\cdot 48$$
$$48=3\cdot 14 + 6$$
$$14=2\cdot 6+2$$
$$6 = 3\cdot 2$$
Zaczynaj±c od przedostatnej równo¶ci i kolejno podstawiaj±c otrzymujemy
$$2= 14 -2\cdot 6= 14 - 2\cdot(48-3\cdot 14)=14-2\cdot 48+6\cdot 14=$$
$$7\cdot 14 - 2\cdot 48=7(62-48)-2\cdot 48=7\cdot 62 - 7\cdot 48 - 2\cdot 48=$$
$$7\cdot 62 - 9\cdot 48$$
a więc $x=7, y=-9$
Tw. 1
Dla dowolnych liczb całkowitych $a, b, c$ równanie
$$ax+by=c$$
ma rozwi±zanie w liczbach całkowitych wtedy i tylko wtedy, gdy
$$d = NWD(a, b) \mid c$$
Dowód
$(\Leftarrow)$
Załóżmy, że $d\mid c$. Wtedy istn. liczba całk. $k$, że $c=d\cdot k$.
Stosuj±c algorytm Euklidesa znajdujemy liczby całkowite $x_{1}, y_{1}$ takie, że $ax_{1}+by_{1}=d$. Wtedy $akx_{1}+bky_{1}=c$.
$(\Rightarrow)$
Załóżmy, że dla pewnych liczb całkowitych $x_{0}, y_{0}, ax_{0} + by_{0} = c$. Wówczas, skoro $d\mid a$ oraz $d\mid b$, to $d\mid ax_{0}+by_{0}$.
Tw. 2
Niech $a, b, c$ będ± dowolnymi liczbami całkowitymi i niech $d=NWD(a, b)\mid c$. Wówczas wszystkie całkowite rozwi±zania równania $ax+by=c$ s± postaci:
$$x = x_{0}+\frac{bt}{d}, y =y_{0} -\frac{at}{d} $$, gdzie $t$ jest dowoln± liczb± całkowit±, a $x_{0}, y_{0}$ jest rozwi±zaniem powstałym z algorytmu Euklidesa.
Dowód
Niech $x_{0}, y_{0}$ będzie rozwi±zaniem równanaia $ax+by = c$. Wtedy $ax+by=c=ax_{0}+by_{0}$. St±d
$a(x-x_{0}) = b(y_{0}-y)$. Po podzieleniu obu stron przez $NWD(a, b)$ mamy
$$a_{1}(x-x_{0})=b_{1}(y_{0}-y)$$
gdzie $a=a_{1}d$ i $b=b_{1}d$ i $a_{1}$ oraz $b_{1}$ s± względnie pierwsze. Wówczas z ostatniej równo¶ci wynika, że $b_{1}\mid x-x_{0}$. Zatem istn. liczba całkowita $t$, że $x-x_{0}= tb_{1}$. St±d $x = x_{0}+t\cdot b_{1}$, czyli $x = x_{0}+\frac{b\cdot t}{d}$. Wstawiamy obliczone $x$ do równiania.
$$a_{1}b_{1}t=b_{1}(y_{0}-y)$$
$$y=y_{0}-a_{1}t=y_{0}-\frac{at}{d}$$
Przykład
W zbiorze liczb całkowitych rozwi±zać równanie:
$$18x+10y = 10$$
Obliczamy NWD(18, 10) z algorytmu Euklidesa
$$18=1\cdot 10+8$$
$$10=1\cdot 8+2$$
$$8=4\cdot 2$$
Zatem NWD(18,10)=2 i $2\mid 10$, czyli równanie ma rozwi±zanie w liczbach całkowitych.
Rozwi±zujemy równanie $$18x+10y=2$$
Z algorytmu Euklidesa mamy kolejno
$2=10 - 8=10-(18-10)=2\cdot 10-1\cdot 18$, czyli $x=-1, y=2$
Mamy, więc $18\cdot (-1) + 10\cdot 2 = 2$. Mnożymy obie strony przez 5
$$18\cdot(-5)+10\cdot 10 = 10$$
Zatem $x_{0}=-5, y_{0}=10$, czyli na mocy Tw.2
$$x = -5+\frac{10}{2}t=-5+5t, y=10-\frac{18}{2}t=10-9t$$
dla dowolnej liczby całkowitej $t$.
powrót do spisu
