Für Primzahlen \( p \) gilt \( a^{p} \equiv a(\bmod p) \). Für Nichtprimzahlen ist diese Kongruenz in der Regel falsch. Leider gibt es aber Nichtprimzahlen, die den Satz von Fermat erfüllen, wir können also nicht Primzahlen schnell erkennen, indem wir \( a^{p}(\bmod p) \) ausrechnen. Hier konstruieren wir eine Reihe von Zahlen, die zusammengesetzt sind, aber den Satz von Fermat erfüllen.
Zeigen Sie: Wenn \( m \) eine ganze Zahl ist, so dass \( 6 m+1, 12 m+1, 18 m+1 \) alle prim sind, dann gilt für \( n=(6 m+1)(12 m+1)(18 m+1) \) und alle \( a \) mit \( (a, n)=1 \), \( \operatorname{dass} a^{n-1} \equiv 1(\bmod n) \).
