Benutzer:Abrankov/Pepin Test Beweis

Da ${}F_{r}-1$ eine Zweierpotenz ist, sind

${}3^{\frac {F_{r}-1}{2}}\equiv -1\mod F_{r}\,\,\,\Rightarrow \,\,\,3^{F_{r}-1}\equiv 1\mod F_{r}\,$

gerade die nötigen Kongruenzen, um mit Hilfe des vorangegangenen Satzes schließen zu können, dass ${}F_{r}$ eine Primzahl ist.

Sei nun umgekehrt vorausgesetzt, dass ${}F_{r}$ eine Primzahl ist, dann ist nach Satz von Euler (Satz 4.5) und dem Gaußschen Reziprozitätsgesetz

${}3^{\frac {F_{r}-1}{2}}\equiv \left({\frac {3}{F_{r}}}\right)=\left({\frac {F_{r}}{3}}\right)\mod F_{r}\,.$

Mit ${}F_{r}=2^{2^{r}}+1\equiv (-1)^{2^{r}}+1=2\equiv -1\mod 3$ folgt

${}3^{\frac {F_{r}-1}{2}}\equiv \left({\frac {F_{r}}{3}}\right)=\left({\frac {-1}{3}}\right)=-1\mod F_{r}\,.$