Bizonyítás

Mindkét oldalhoz $as$-t hozzáadva azt kaptuk tehát, hogy az $ax\equiv b\pmod m$ kongruencia akkor és csak akkor oldható meg, ha létezik olyan $(s;t)$ egész számpár, amely megoldása lineáris diofantoszi egyenletnek:

A fentiekből továbbá kiderült, hogy ekkor – és csakis ekkor – az $[s]_m$ maradékosztály valóban megoldása az $ax\equiv b\pmod m$ lineáris kongruenciának.

Végül azt igazoljuk, hogy az $ax+my=b$ egyenlet – és az eddigiek miatt az $ax\equiv b\pmod m$ kongruencia – megoldhatóságának szükséges és elégséges feltétele az $(a,m)|b$ oszthatóság. Tegyük ezért fel, hogy az $x_0$, $y_0$ számpár egy megoldása ennek az egyenletnek, azaz:

Mivel az $(a,m)$ az $a$ és $m$ közös osztója, ezért nyilván fennállnak az $(a,m)|a$ és $(a,m)|m$ oszthatóságok. Emiatt a 16.2. Tétel 7. és 6. pontja alapján valóban fennáll az alábbi oszthatóság is:

Visszafelé: Ha fennáll az $(a,m)|b$ oszthatóság, az azt jelenti, hogy létezik olyan $t$ egész szám, amelyre teljesül az alábbi egyenlet:

Mivel $\Z$ a 19.15. Tétel alapján főideálgyűrű, ezért alkalmazható a 20.11. Tétel. Ez alapján az $(a,m)$ kitüntetett közös osztóhoz léteznek olyan $u$ és $v$ egész számok, hogy teljesül az alábbi:

Ezt behelyettesíthetjük az előző egyenletbe:

A zárójelet felbontva végül ezt kapjuk: