Elsőként megmutatjuk, hogy az ax\equiv b\pmod m lineáris kongruencia pontosan akkor oldható meg, amikor megoldható az ax+my=b lineáris diofantoszi egyenlet.

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. Az oszthatóság 16.1. Definíció definíciója miatt ez pontosan azt jelenti, hogy létezik olyan t egész szám, amelyre teljesül az mt=b-as egyenlet. Mindkét oldalhoz as-t hozzáadva azt kapjuk tehát, hogy az ax\equiv b\pmod m kongruencia megoldhatósága pontosan azt jelenti, hogy léteznek olyan s és t egész számok, amelyek kielégítik az alábbi lineáris diofantoszi egyenletet:

ax+my=b

Az utóbbi megoldhatóságának szükséges és elégséges feltétele ezért egyúttal az előbbi megoldhatóságának is szükséges és elégséges feltétele lesz – épp ahogyan a tétel állítja. A fentiekből továbbá kiderült, hogy egy s egész szám által reprezentált [s]_m maradékosztály valóban akkor és csak akkor megoldása az ax\equiv b\pmod m lineáris kongruenciának, ha létezik olyan t egész szám, amelyre fennáll az as+mt=b egyenlőség.

Most azt igazoljuk, hogy az ax+my=b egyenlet 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 egész számpár egy megoldása ennek az egyenletnek, azaz:

ax_0+my_0=b

Mivel az (a,m) az a és m egész számok 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. pontja alapján fennállnak az (a,m)|ax_0 valamint az (a,m)|my_0 oszthatóságok is. Ám ekkor ugyanezen tétel 6. pontja miatt fennáll az alábbi oszthatóság is:

(a,m)|\underbrace{ax_0 +my_0}_{=b}

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:

(a,m)\cdot t=b

Mivel az egész számok \Z gyűrűje főideálgyűrű (19.16. Tétel), ezért alkalmazható a Bézout-lemma (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:

(a,m)=au+mv

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

(\underbrace{au+mv}_{(a,m)})\cdot t=b

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

a\cdot (ut) + m\cdot (vt)=b

Azaz lényegében megkaptuk az ax+my=b lineáris diofantoszi egyenlet egy megoldását, nevezetesen az x=ut, y=vt egész számpárt.