youproof.orgDeep Math. Human Access.

21.2. Tétel

Lineáris diofantoszi egyenlet összes megoldása

Legyenek aa, bb és mm tetszőleges egész számok úgy, hogy aa és mm közül legalább az egyik nemnulla. Tegyük fel továbbá, hogy az alábbi lineáris diofantoszi egyenlet megoldható:

ax+my=bax+my=b

Jelöljük m(a,m)\frac{m}{(a,m)}-mel illetve a(a,m)\frac{a}{(a,m)}-mel azokat az egész számokat, amelyeket az (a,m)(a,m) kitüntetett közös osztóval megszorozva rendre az mm illetve az aa 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=sx=s, y=ty=t számpár egy megoldás, akkor tetszőleges kk egész szám esetén az alábbi számpár is egy megoldás:
x=s+k⋅m(a,m)y=t−k⋅a(a,m)\begin{aligned}x&=s+k\cdot \frac{m}{(a,m)} \\ y&=t-k\cdot \frac{a}{(a,m)}\end{aligned}
3.
Ha az x=s1x=s_1, y=t1y=t_1 számpár valamint az x=s2x=s_2, y=t2y=t_2 számpár két tetszőleges megoldás, akkor létezik olyan kk egész szám, amelyre igaz az alábbi:
s2=s1+k⋅m(a,m)t2=t1−k⋅a(a,m)\begin{aligned}s_2&=s_1+k\cdot \frac{m}{(a,m)} \\ t_2&=t_1-k\cdot \frac{a}{(a,m)}\end{aligned}

♣