Pseudo-Primzahlen/Carmichael/Einführung/Textabschnitt

Als Pseudo-Primzahlen bezeichnet man grob gesprochen solche Zahlen, die zwar nicht prim sind, aber wesentliche Eigenschaften mit Primzahlen gemeinsam haben.

Definition

Eine natürliche Zahl ${}n$ heißt quasiprim zur Basis ${}a$, wenn ${}a^{n-1}=1$ modulo ${}n$ gilt.

Definition

Eine natürliche Zahl ${}n$, die nicht prim ist, und die die Eigenschaft besitzt, dass für jede zu ${}n$ teilerfremde ganze Zahl ${}a$

${}a^{n-1}=1\mod n\,$

gilt, heißt Carmichael-Zahl.

Eine Carmichael-Zahl hat also die Eigenschaft, dass sie quasiprim zu jeder zu ${}n$ teilerfremden Basis ${}a$ ist.

Satz

Eine natürliche nicht-prime Zahl ${}n\geq 2$ ist genau dann eine Carmichael-Zahl, wenn jeder Primteiler ${}p$ von ${}n$ einfach ist und ${}p-1$ die Zahl ${}n-1$ teilt.

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.

$\Box$

Beispiel

Die kleinste Carmichael-Zahl ist

${}561=3\cdot 11\cdot 17\,.$

Dies folgt aus Fakt, da ${}2$, ${}10$ und ${}16$ Teiler von ${}560$ sind.

Es ist inzwischen bekannt, dass es unendlich viele Carmichael-Zahlen gibt.