21.2. Tétel
Lineáris diofantoszi egyenlet összes megoldása
Legyenek a, b és m tetszőleges egész számok úgy, hogy a és m közül legalább az egyik nemnulla. Tegyük fel továbbá, hogy az alábbi lineáris diofantoszi egyenlet megoldható:
ax+my=b
Jelöljük \frac{m}{(a,m)}-mel illetve \frac{a}{(a,m)}-mel azokat az egész számokat, amelyeket az (a,m) kitüntetett közös osztóval megszorozva rendre az m illetve az a egész számot kapjuk eredményül. Ekkor igazak az alábbiak:
1.
Az egyenlet egyik megoldását magkaphatjuk a 21.1. Tétel bizonyításában ismertetett kibővített euklidészi algoritmus segítségével.
2.
Ha az x=s, y=t számpár egy megoldás, akkor tetszőleges k egész szám esetén az alábbi számpár is egy megoldás:
\begin{aligned}x&=s+k\cdot \frac{m}{(a,m)} \\ y&=t-k\cdot \frac{a}{(a,m)}\end{aligned}
3.
Ha az x=s_1, y=t_1 számpár valamint az x=s_2, y=t_2 számpár két tetszőleges megoldás, akkor létezik olyan k egész szám, amelyre igaz az alábbi:
\begin{aligned}s_2&=s_1+k\cdot \frac{m}{(a,m)} \\ t_2&=t_1-k\cdot \frac{a}{(a,m)}\end{aligned}
♣