Benutzer:Abrankov/Pocklington Test/Fakt

Sei ${}n$ eine natürliche Zahl, so dass ${}n-1$ eine Faktorisierung der Form ${}n-1=RF$ besitzt, wobei alle Primteiler von ${}F$ bekannt sind. Weiterhin gebe es eine natürliche Zahl ${}0<a<n$ mit

1. ${}a^{n-1}\equiv 1\mod n$
2. ${}{ggT}\,(a^{\frac {n-1}{q}}-1,n)=1$

für alle Primteiler ${}q$ von ${}F$. Ist dann ${}F\geq {\sqrt {n}}$, so ist ${}n$ eine Primzahl.