Bizonyítás
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:
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
Mivel a kongruencia a 20.2. Tétel 2. és 3. pontja alapján szimmetrikus és tranzitív, ezért ez ekvivalens az alábbival:
A 20.3. Tétel alapján mindkét oldalt egyszerűsíthetjük a-val, ám eközben az m modulust is "el kell osztanunk" az (a,m) kitüntetett közös osztóval, azaz jelen esetben d-vel. Az előző kongruencia tehát ekvivalens az alábbival:
Vagyis a t által reprezentált [t]_m maradékosztály akkor és csak akkor lesz megoldás, ha t ugyanabba a modulo \frac{m}{d} maradékosztályba esik, mint s, azaz:
Ez a 20.4. Tétel alapján akkor és csak akkor teljesül, ha t felírható az alábbi alakban valamilyen alkalmasan választott k egész számmal:
Azt kaptuk tehát, hogy amennyiben ismerünk egy [s]_m megoldást, akkor az összes többi megoldást előállíthatjuk
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ály reprezentánselemeit kapjuk.
Nézzük meg ezért, hogy két tetszőleges 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:
Ez ugye pontosan akkor teljesül, ha fennáll az alábbi kongruencia:
A 20.2. Tétel 5. pontja miatt mindkét oldalból kivonhatunk s-t:
A 20.3. Tétel alapján mindkét oldalt egyszerűsíthetjük \frac{m}{d}-vel. Vigyázat! A tétel szerint ilyenkor ugyanis a modulust is egyszerűsíteni kell \frac{m}{d} és m kitüntetett közös osztójával. Azaz az előbbi kongruencia akkor és csak akkor akkor teljesül, amikor az alábbi kongruencia is:
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 jelenleg a \Z gyűrűben vagyunk, ahol nem értelmezhető az "osztás". 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:
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.6. Tétel 2. pontja miatt \frac{m}{d} asszociáltja, és emiatt lecserélhető vele. A fenti kongruenciában szereplő modulus tehát így hozható egyszerűbb formára:
Ez tehát azt az egész számot jelöli, amelyet az \frac{m}{d} egész számmal 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:
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 is megegyeznek. Az ax\equiv b\pmod m lineáris kongruenciának tehát pontosan annyi megoldása van, 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 tétel 2. állításában szereplő maradékosztályokat kapjuk megoldásként.
∎