Elegendő a 2. állítást igazolni, abból ugyanis automatikusan következik a megoldásszámra vonatkozó 1. állítás. Azt mondtuk, hogy az s egész szám által reprezentált [s]_m maradékosztály megoldása a kongruenciának, azaz:

as\equiv b\pmod m

Válasszunk most egy tetszőleges t egész számot. Az általa reprezentált [t]_m maradékosztály akkor és csak akkor lesz megoldása a kongruenciának, ha teljesül at\equiv b\pmod m. Mivel a kongruencia szimmetrikus és tranzitív (20.2. Tétel 2. és 3. pont), ezért ez pontosan az alábbit jelenti:

as\equiv at\pmod m

A kongruenciák egyszerűsítéséről szóló 20.3. Tétel alapján mindkét oldalt egyszerűsíthetjük a-val, ám eközben a modulust is „el kell osztanunk” az (a,m) kitüntetett közös osztóval, azaz jelen esetben d-vel. A fenti kongruencia tehát pontosan az alábbi esetben teljesül:

s\equiv t\pmod{\frac{m}{d}}

Vagyis a t által reprezentált [t]_m maradékosztály pontosan akkor lesz megoldás, ha t ugyanabba a modulo \frac{m}{d} maradékosztályba esik, mint s, azaz:

[s]_{\frac{m}{d}}=[t]_{\frac{m}{d}}

Ez a 20.4. Tétel alapján épp azt jelenti, hogy t felírható az alábbi alakban valamilyen alkalmasan választott k egész számmal:

t=s+k\cdot \frac{m}{d}

Azt kaptuk tehát, hogy amennyiben ismerünk egy [s]_m megoldást, akkor az összes többi megoldást előállíthatjuk [s+k\cdot \frac{m}{d}]_m alakban. Így már csak azt kell igazolni, hogy k-val végigfutva az összes egész számon épp a tétel 2. állításában szereplő d darab modulo m maradékosztályt kapjuk.

Nézzük meg ezért, hogy két különböző k_1 és k_2 esetén az s+k_1\frac{m}{d} és s+k_2\frac{m}{d} kifejezések mikor fogják ugyanazt a maradékosztályt reprezentálni, azaz mikor fog teljesülni az alábbi:

[s+k_1\frac{m}{d}]_m=[s+k_2\frac{m}{d}]_m

Ez ugye pontosan akkor teljesül, ha fennáll az alábbi kongruencia:

s+k_1\frac{m}{d}\equiv s+k_2\frac{m}{d} \pmod m

A 20.2. Tétel 6. pontja miatt mindkét oldalból kivonhatunk s-t:

k_1\frac{m}{d}\equiv k_2\frac{m}{d} \pmod m

A 20.3. Tétel alapján mindkét oldalt egyszerűsíthetjük \frac{m}{d}-vel. Vigyáznunk kell azonban, mivel ilyenkor ugye a modulust is egyszerűsíteni kell \frac{m}{d} és m kitüntetett közös osztójával! Azaz a fenti kongruencia pontosan akkor teljesül, amikor az alábbi kongruencia is:

k_1\equiv k_2 \pmod{\frac{m}{(\frac{m}{d}, m)}}

Most vizsgáljuk meg, hogy tulajdonképpen mivel egyezik meg az itt szereplő modulus. Ne feledjük, hogy itt nem törtekről van szó, hiszen az egész számok \Z gyűrűjében vagyunk, ahol nem értelmezhető az osztás művelete. Ehelyett például az \frac{m}{d} csak egy jelölés, amely azt az egész számot jelöli, amellyel a d egész számot megszorozva az m egész számot kapjuk eredményül. Azaz:

\frac{m}{d} \cdot d = m

Feltéve persze, ha ilyen létezik, aminek ugye a feltétele az d|m oszthatóság. Ez jelen esetben nyilván fennáll, mivel azt mondtuk, hogy d az a és m kitüntetett közös osztója. Ám ekkor teljesül az \frac{m}{d}|m oszthatóság is, így az (\frac{m}{d},m) kitüntetett közös osztó a 17.5. Tétel 4. pontja miatt \frac{m}{d}-vel egyezik meg. A fenti kongruenciában tehát a modulus így hozható egyszerűbb formára:

\frac{m}{(\frac{m}{d}, m)}=\frac{m}{(\frac{m}{d})}

Ez tehát azt az egész számot jelöli, amellyel az \frac{m}{d} egész számot megszorozva az m egész számot kapjuk eredményül. A fentebbi \frac{m}{d} \cdot d = m összefüggés alapján ez épp d-vel egyezik meg. A fenti kongruencia tehát tulajdonképpen így néz ki:

k_1\equiv k_2\pmod d

Azt kaptuk tehát, hogy az [s+k_1\frac{m}{d}]_m és [s+k_2\frac{m}{d}]_m modulo m maradékosztályok akkor és csak akkor egyeznek meg, amikor a [k_1]_d és [k_2]_d modulo d maradékosztályok megegyeznek.

Ez viszont pontosan azt jelenti, hogy épp annyi megoldása van az ax\equiv b\pmod m lineáris kongurenciának, ahány modulo d maradékosztály létezik, ezek száma viszont a 20.4. Tétel alapján d. Így tehát ha k végigfut a 0, 1, 2, …, d-1 egész számokon, akkor épp a 2. állításban szereplő [s]_m, [s+\frac{m}{d}]_m, [s+2\frac{m}{d}]_m, …, [s+(d-1)\frac{m}{d}]_m maradékosztályokat kapjuk megoldásként.