.png)
Rozszerzony algorytm Eukliedesa
Liczby wygenerowane przez algorytm Euklidesa pozwalają wyznaczye liczby całkowite $x, y$ takie, że $$ax+by=NWD(a, b)$$ PrzykładRozwiązae 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ódNiech $x_{0}, y_{0}$ będzie rozwiązaniem równania $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ązae 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$.
$$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
