Rozwiąż w liczbach całkowitych równania:
1) 3x+4y=13,
2) 31x+11y=2,
3) 25x+100y=6,
4) 39x-13y=111,
5) 122x+129y=2.
Czy ktoś mógłby pokazać ogólny algorytm rozwiązywania takich równań? Najlepiej na przykładzie innym od pierwszego .
Kilka równań diofantycznych stopnia pierwszego
- DEXiu
- Użytkownik
- Posty: 1174
- Rejestracja: 17 lut 2005, o 17:22
- Płeć: Mężczyzna
- Lokalizacja: Jaworzno
- Pomógł: 69 razy
Kilka równań diofantycznych stopnia pierwszego
Przede wszystkim równanie diofantyczne pierwszego stopnia postaci \(\displaystyle{ ax+by=c}\) ma rozwiązanie w liczbach całkowitych wtw., gdy \(\displaystyle{ NWD(a,b)|c}\) (to tak ku przypomnieniu) - zatem przypadki 3) i 4) odpadają od razu
Ogólny algorytm może być np. taki: (przyjmiemy bez straty ogólności, że \(\displaystyle{ {a}\leq{b}}\))
\(\displaystyle{ ax+by=c\\a(x+y)+(b-a)y=c\\{t:=x+y}\Rightarrow{x=t-y}\\at+(b-a)y=c\\\left{\begin{array}{l}y=\frac{c-at}{b-a}\\x=t-\frac{c-at}{b-a}=\frac{(2a+b)t-c}{b-a}\end{array}\,,\,t\in\mathbb{Z}}\)
Ogólny algorytm może być np. taki: (przyjmiemy bez straty ogólności, że \(\displaystyle{ {a}\leq{b}}\))
\(\displaystyle{ ax+by=c\\a(x+y)+(b-a)y=c\\{t:=x+y}\Rightarrow{x=t-y}\\at+(b-a)y=c\\\left{\begin{array}{l}y=\frac{c-at}{b-a}\\x=t-\frac{c-at}{b-a}=\frac{(2a+b)t-c}{b-a}\end{array}\,,\,t\in\mathbb{Z}}\)