Wiem ,że \(\displaystyle{ NWD(12378,3054)=6}\)
Stosując algorytm Euklidesa dostaję jedno rozwiązanie równania
\(\displaystyle{ x *12378+ y*3054 = 6}\)
mianowicie \(\displaystyle{ x=132, y=-535}\)
W jaki sposób otrzymać wszystkie rozwiązania powyższego równania?
rozszerzony algorytm Euklidesa
rozszerzony algorytm Euklidesa
jeśli \(\displaystyle{ (x_0, y_0)}\) spełnia :
\(\displaystyle{ x \cdot a + y \cdot b = NWD(a,b)}\)
to wszystkie takie pary (x,y) też spełniają :
\(\displaystyle{ (x_0 + k\cdot \frac{NWW(a,b)}{a}; y_0 - k \cdot \frac{NWW(a,b)}{b}), k \in \mathbb{Z}.}\)
i są to wszystkie rozwiązania
\(\displaystyle{ x \cdot a + y \cdot b = NWD(a,b)}\)
to wszystkie takie pary (x,y) też spełniają :
\(\displaystyle{ (x_0 + k\cdot \frac{NWW(a,b)}{a}; y_0 - k \cdot \frac{NWW(a,b)}{b}), k \in \mathbb{Z}.}\)
i są to wszystkie rozwiązania