Episode I

Alice és Bob

. rész: Nem Miller-Rabin-tanúk csoportjára vonatkozó lemma prímhatványok esetén

Legyen p egy pozitív, páratlan prímszám, c pedig egy pozitív kitevő, továbbá r egy tetszőleges olyan egész szám, amelyre teljesül az alábbi konguencia:

r^{p-1}\equiv 1\pmod{p^c}

Jelöljük P_r-rel az összes olyan egész szám halmazát, amelyeket x helyére behelyettesítve fennáll mindkét alábbi kongruencia:

\begin{aligned}x&\equiv r\pmod{p^c} \\ x^{p-1}&\equiv 1\pmod{p^{c+1}}\end{aligned}

Ekkor a P_r halmaz épp egy modulo p^{c+1} maradékosztállyal egyezik meg.

Kapcsolódó oldal:
Érintő - Elektronikus Matematikai Lapok