Carmichael Zahlen/Charakterisierung mit Primteilern/Fakt/Beweis

Beweis

Es sei ${}n=p_{1}^{r_{1}}\cdots p_{k}^{r_{k}}$ die kanonische Primfaktorzerlegung. Nach dem chinesischen Restsatz ist

${}{\left(\mathbb {Z} /(n)\right)}^{\times }\cong {\left(\mathbb {Z} /(p_{1}^{r_{1}})\right)}^{\times }\times \cdots \times {\left(\mathbb {Z} /(p_{k}^{r_{k}})\right)}^{\times }\,.$

Es sei ${}a=(a_{1},\ldots ,a_{k})$ eine zu ${}n$ teilerfremde Zahl und sei vorausgesetzt, dass ${}n$ eine Carmichael-Zahl ist. Dann ist insbesondere

${}(a_{i})^{n-1}=1\mod p_{i}^{r_{i}}\,$

für jeden Index ${}i$. Wählt man für ${}a_{i}$ ein primitives Element in ${}\mathbb {Z} /(p_{i}^{r_{i}})$ (was nach Fakt möglich ist; für ${}p_{i}=2$ ist nichts zu zeigen), so hat dies die Ordnung ${}(p_{i}-1)p_{i}^{r_{i}-1}$. Da ${}n-1$ ein Vielfaches der Ordnung ist und da ${}p_{i}$ und ${}n-1$ teilerfremd sind, folgt, dass ${}n-1$ ein Vielfaches von ${}p-1$ ist. Bei ${}r_{i}\geq 2$ gibt es Elemente der Ordnung ${}p_{i}$ in ${}{\left(\mathbb {Z} /(p_{i}^{r_{i}})\right)}^{\times }$ (auch bei ${}p=2$), und es ergibt sich der Widerspruch ${}p{|}(n-1)$. Also sind alle Exponenten einfach.

Für die Umkehrung ist nach Voraussetzung ${}r_{i}=1$. Es sei wieder ${}a=(a_{1},\ldots ,a_{k})$ eine Einheit. Dann ist

${}a^{n-1}=\left(a_{1}^{n-1},\,\ldots ,\,a_{k}^{n-1}\right)=\left({\left(a_{1}^{p_{1}-1}\right)}^{\frac {n-1}{p_{1}-1}},\,\ldots ,\,{\left(a_{k}^{p_{k}-1}\right)}^{\frac {n-1}{p_{k}-1}}\right)=\left(1,\,\ldots ,\,1\right)=1\,.$

Also ist ${}n$ eine Carmichael-Zahl.

Zur bewiesenen Aussage