Bizonyítás
Az ax\equiv b\pmod m megoldhatósága azt jelenti, hogy létezik olyan [s]_m maradékosztály, amely megoldása ennek a kongruenciának. Az [s]_m maradékosztályt tehát az s egész számmal reprezentáltuk, azaz teljesül az as\equiv b\pmod m kongruencia. Ez viszont a 20.1. Tétel 3. pontja alapján pontosan akkor teljesül, ha fennáll az m|b-as oszthatóság. A 16.1. Definíció alapján ez pontosan akkor teljesül, ha létezik olyan t egész szám, amelyre teljesül az mt=b-as egyenlet.
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:
Azaz lényegében megkaptuk az ax+my=b lineáris diofantoszi egyenlet egy megoldását, nevezetesen az x=ut, y=vt számpárt.
∎