Episode I

Alice és Bob

. rész: Lineáris kongruenciák megoldásai és megoldásszáma

Moldvai Dávid · Posted on

Legyen a és b tetszőleges, m\gt 0 pedig valamilyen pozitív egész szám. Jelöljük továbbá az a és m egész számok 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 kongruencia megoldható, akkor a 20.8. Definíció szerinti értelemben vett megoldásszá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 kongruenciának, akkor pontosan az alábbi – egymástól páronként különböző – maradékosztályok lesznek a kongruencia megoldásai:
\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.