rozszerzony algorytm Euklidesa

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Awatar użytkownika
wiosna
Użytkownik
Użytkownik
Posty: 98
Rejestracja: 2 maja 2008, o 14:01
Płeć: Kobieta
Lokalizacja: poznań
Podziękował: 20 razy
Pomógł: 1 raz

rozszerzony algorytm Euklidesa

Post autor: wiosna » 9 lut 2009, o 16:39

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?

winemore
Użytkownik
Użytkownik
Posty: 38
Rejestracja: 3 lut 2009, o 20:31
Płeć: Mężczyzna
Pomógł: 8 razy

rozszerzony algorytm Euklidesa

Post autor: winemore » 9 lut 2009, o 18:45

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

ODPOWIEDZ