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.