Bizonyítás

Először is a 23.9. Definíció értelmében (\Z/n\Z)^{\times} minden eleme vagy Miller-Rabin-tanú, vagy Miller-Rabin-nemtanú. Elegendő tehát azt megmutatnunk, hogy (\Z/n\Z)^{\times} elemeinek legfeljebb a fele Miller-Rabin-nemtanú.

A 24.17. Tételnek megfelelően jelölje G_n az n Miller-Rabin-nemtanúinak halmazát, H_n pedig a 24.16. Tételben bevezetett részcsoportot (\Z/n\Z)^{\times}-ben. Ekkor a 24.17. Tétel szerint G_n\sube H_n. A H_n részcsoport prímhatvány esetben a 24.20. Tétel miatt, egyéb esetekben pedig a 24.22. Tétel 3. és 4. pontja miatt egy valódi részcsoport. Azaz:

G_n\sube H_n\lt (\Z/n\Z)^{\times}

A Lagrange-tétel szerint H_n rendje osztója a (\Z/n\Z)^{\times} csoport rendjének, azaz teljesül az alábbi összefüggés, ahol r a H_n részcsoport indexe (\Z/n\Z)^{\times}-ben:

r\cdot |H_n| = |(\Z/n\Z)^{\times}|

Mivel H_n valódi részcsoport, ezért |H_n|\lt |(\Z/n\Z)^{\times}|, így r\geq 2. Igaz tehát az alábbi egyenlőtlenség:

2\cdot |H_n|\leq |(\Z/n\Z)^{\times}|

Továbbá a 24.17. Tétel miatt G_n\sube H_n, ezért |G_n|\leq |H_n|, és így:

2\cdot |G_n|\leq 2\cdot |H_n|

A két egyenlőtlenséget összevetve megkapjuk a tétel állítását:

2\cdot |G_n|\leq |(\Z/n\Z)^{\times}

Azaz a redukált maradékosztályoknak legfeljebb a fele lehet Miller-Rabin-nemtanú. Másként fogalmazva legalább a felük Miller-Rabin-tanú kell legyen.

∎

Iratkozz fel a hírlevelünkre