youproof.orgDeep Math. Human Access.

Bizonyítás

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

n−1=2e⋅kn-1=2^e\cdot k

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

a2e⋅k⏞=n−1≡1(modn)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∣a2e⋅k−1n|a^{2^e\cdot k}-1

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

n∣(ak−1)⋅(ak+1)⋅(a2k+1)⋅(a4k+1)⋅…⋅(a2e−1k+1)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 nn 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:

n∣ak−1n∣ak+1n∣a2k+1n∣a4k+1⋮n∣a2e−1k+1\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:

ak≡+1(modn)ak≡−1(modn)a2k≡−1(modn)a4k≡−1(modn)⋮a2e−1k≡−1(modn)\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[a]_n maradékosztály Miller-Rabin-nemtanú.

∎