20.14. Tétel
Lineáris kongruenciák megoldásai és megoldásszáma
Legyen a és b tetszőleges, 0\lt m pedig pozitív egész szám. Jelöljük továbbá az a és m pozitív kitüntetett közös osztóját d-vel, azaz d=(a,m). Ekkor igazak az alábbi állítások:
1.
Ha az ax\equiv b\pmod m lineáris kongruencia megoldható, akkor a 20.8. Definíció szerinti értelemben vett megoldások száma d.
2.
Ha egy valamilyen s egész szám által reprezentált [s]_m maradékosztály megoldása az ax\equiv b\pmod m lineáris kongruenciának, akkor pontosan az alábbi – egymástól páronként különböző – maradékosztályok alkotják az összes megoldást:
\begin{aligned}
&[s+0\cdot \frac{m}{d}]_m \\
&[s+1\cdot \frac{m}{d}]_m \\
&[s+2\cdot \frac{m}{d}]_m \\
&[s+3\cdot \frac{m}{d}]_m \\
&\vdots \\
&[s+(d-1)\cdot \frac{m}{d}]_m
\end{aligned}
Itt \frac{m}{d} alatt azt az egész számot értjük, amelyet a d=(a,m) kitüntetett közös osztóval megszorozva az m modulust kapjuk eredményül, azaz amelyre teljesül, hogy
\frac{m}{d}\cdot d = m
♣