.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\cdot\\ \cdot(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 istnieje 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ównania. $$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ązanie 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