youproof.orgDeep Math. Human Access.

Bizonyítás

Legyen n\gt 1 egy tetszőleges páratlan prímszám, továbbá legyen adva egy tetszőleges [a]_n redukált maradékosztály. Képezzük azt az e\geq 1 kitevőt és k\geq 1 páratlan egész számot, amelyekre teljesülnek az alábbiak:

n-1=2^e\cdot k

Mivel n prím, továbbá a és n relatív prímek – hiszen [a]_n redukált –, ezért a kis Fermat-tétel alapján teljesül rá az alábbi kongruencia:

a^{\overbrace{2^e\cdot k}^{=n-1}}\equiv 1\pmod n

Ez a 20.1. Tétel 3. pontja értelmében azt jelenti, hogy teljesül az alábbi oszthatóság:

n|a^{2^e\cdot k}-1

Az oszthatóság jobboldalán szereplő kifejezést a 23.8. Tétel szerint szorzatra bonthatjuk:

n|(a^k-1)\cdot (a^k+1)\cdot (a^{2k}+1)\cdot (a^{4k}+1)\cdot \ldots \cdot (a^{2^{e-1}k}+1)

Mivel n prím, ezért a 16.13. Definíció utáni megjegyzés szerint legalább az egyik jobboldali tényezőnek osztója kell legyen. Azaz az alábbi oszthatóságok közül legalább az egyiknek teljesülnie kell:

\begin{aligned}n&|a^k-1 \\ n&|a^k+1 \\ n&|a^{2k}+1 \\ n&|a^{4k}+1 \\ &\vdots \\ n&|a^{2^{e-1}k}+1 \end{aligned}

A 20.1. Tétel 3. pontja alapján ez tehát azt jelenti, hogy legalább az egyik kongruenciának teljesülnie kell az alábbiak közül:

\begin{aligned}a^k\equiv +1\pmod n \\ a^k\equiv -1\pmod n \\ a^{2k}\equiv -1\pmod n \\ a^{4k}\equiv -1\pmod n \\ &\vdots \\ a^{2^{e-1}k}\equiv -1\pmod n \end{aligned}

Ez viszont a 23.9. Definíció szerint épp azt jelenti, hogy az [a]_n maradékosztály Miller-Rabin-nemtanú.

∎