Dowód na ogólne całkowite rozwiązanie równania 𝑎𝑥 + 𝑏𝑦 = 𝑁 [duplikat]

Dec 26 2020

Dany $a,b\in\mathbb{Z}-\{0\}$ i $N\in\mathbb{Z}$łatwo to pokazać, jeśli $x_0,y_0\in\mathbb{Z}$ są szczególnym rozwiązaniem $ax+by=N$, następnie $x=x_0+\frac{b}{d}t$ i $y=y_0-\frac{a}{d}t$, gdzie $d=gcd(a,b)$ i $t\in\mathbb{Z}$, są również rozwiązaniem $ax+by=N$.

Ale czy mogę zapytać, jak udowodnić, że są one w rzeczywistości ogólnym rozwiązaniem $ax+by=N$ jeśli ograniczymy rozwiązania w środku $\mathbb{Z}$? (tj. wszystkie rozwiązania całkowite zostały policzone)

Dzięki!

Odpowiedzi

2 AmeetSharma Dec 26 2020 at 15:39

Niech A będzie zbiorem rozwiązań całkowitych wszystkich uporządkowanych par. Niech B będzie zbiorem wszystkich uporządkowanych par rozwiązań liczb całkowitych tylko w podanej przez Ciebie postaci. Wiemy$B \subseteq A$

Najpierw znajdź wszystkie racjonalne rozwiązania równania, a następnie ogranicz je.

Pozwolić

$x=x_0+bu$

dla $u \in\mathbb{Q}$

Można to rozwiązać dla u dla dowolnego racjonalnego x.

A potem używając

$ax+by=N$

$a(x_0+bu)+by=N$

$y=\frac{N-a(x_0+bu)}{b}$

$y=\frac{by_0-abu}{b} = y_0-au$, co również jest racjonalne.

Więc każdy element A można zapisać jako $(x_0+bu,y_0-au)$ dla jakiegoś racjonalnego u.

Więc pozwól $(x_0+bu,y_0-au) \in A$

My wymagamy

$bu \in \mathbb{Z}$

$au \in \mathbb{Z}$

pisać $u=\frac{m}{n}$. Załóżmy, że jest to najgorsze

Więc

$\frac{bm}{n} \in \mathbb{Z}$

$\frac{am}{n} \in \mathbb{Z}$

Więc $n|b$ i $n|a$

To znaczy $n|d$ gdzie $d=gcd(a,b)$

Możemy pisać $rn=d$ dla jakiejś liczby całkowitej r

Więc $n = \frac{d}{r}$

$\frac{bm}{n} = \frac{b}{d}(rm)$

$\frac{am}{n} = \frac{a}{d}(rm)$

Więc pozwalając $t=rm$, wiemy to $(x_0+\frac{b}{d}t,y_0-\frac{a}{d}t) \in B$

Więc $A \subseteq B$ dając nam $A=B$.