youproof.orgDeep Math. Human Access.

20.14. Tétel

Lineáris kongruenciák megoldásai és megoldásszáma

Legyen aa és bb tetszőleges, 0<m0\lt m pedig pozitív egész szám. Jelöljük továbbá az aa és mm pozitív kitüntetett közös osztóját dd-vel, azaz d=(a,m)d=(a,m). Ekkor igazak az alábbi állítások:

1.
Ha az ax≡b(modm)ax\equiv b\pmod m lineáris kongruencia megoldható, akkor a 20.8. Definíció szerinti értelemben vett megoldások száma dd.
2.
Ha egy valamilyen ss egész szám által reprezentált [s]m[s]_m maradékosztály megoldása az ax≡b(modm)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:
[s+0⋅md]m[s+1⋅md]m[s+2⋅md]m[s+3⋅md]m⋮[s+(d−1)⋅md]m\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 md\frac{m}{d} alatt azt az egész számot értjük, amelyet a d=(a,m)d=(a,m) kitüntetett közös osztóval megszorozva az mm modulust kapjuk eredményül, azaz amelyre teljesül, hogy

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

♣