Primzahlen: I. Kapitel: Die Eigenschaften der Primzahl

Dass eine Primzahl eine natürliche Zahl größer eins ist, die nur durch eins und sich selbst teilbar ist, kann man als Eigenschaft der Primzahl bezeichnen. Es ist die Eigenschaft, über die sich die Primzahl definiert. Daneben hat die Primzahl noch eine Menge anderer Eigenschaften. Einige dieser Eigenschaften sind trivial, haben aber Auswirkungen auf Zahlen, die aus diesen Primzahlen zusammengesetzt sind. Andere Eigenschaften treffen auch auf Zahlen zu, die keine Primzahlen sind, und die deswegen nur bedingt als Primzahlkriterium eingesetzt werden können.

Außer 2 ist jede Primzahl ungerade und hat deshalb die Form ${\displaystyle 4n+1}$ oder ${\displaystyle 4n-1}$. Auf äquivalente Weise könnte man sagen eine ungerade Zahl hat die Form ${\displaystyle 4n+1}$ oder ${\displaystyle 4n+3}$, denn ${\displaystyle 4n+3=4(n+1)-1=4n'-1}$. Die beiden möglichen Formen spielen eine unterschiedliche Rolle bei ungeraden, zusammengesetzten natürlichen Zahlen.

Wenn eine solche Zahl die Form ${\displaystyle 4n-1\ }$ besitzt, muss sie eine ungerade Anzahl an Primfaktoren der Form ${\displaystyle 4p-1\ }$ besitzen, also mindestens einen Primfaktor dieser Form.

Eine ungerade natürliche Zahl der Form ${\displaystyle 4n+1\ }$ wiederum hat entweder keine Primfaktoren der Form ${\displaystyle 4p-1\ }$ oder ihre Anzahl ist gerade.

Das lässt sich über folgende Sätze zeigen:

Das Produkt zweier Zahlen der Form ${\displaystyle 4n-1}$ hat die Form ${\displaystyle 4n+1}$

${\displaystyle (4n-1)(4m-1)=16nm-4(n+m)+1=4(4nm-n-m)+1=4k+1}$

Das Produkt zweier Zahlen der Form ${\displaystyle 4n+1}$ hat die Form ${\displaystyle 4n+1}$

${\displaystyle (4n+1)(4m+1)=16nm+4(n+m)+1=4(4nm+n+m)+1=4k'+1}$

Das Produkt einer Zahl der Form ${\displaystyle 4n-1}$ und einer Zahl der Form ${\displaystyle 4n+1}$ hat die Form ${\displaystyle 4n-1}$

${\displaystyle (4n-1)(4m+1)=16nm+4(n-m)-1=4(4nm+n-m)-1=4k''-1}$

Primzahlen, die größer als drei sind, haben entweder die Form ${\displaystyle 6n+1}$ oder ${\displaystyle 6n-1}$. Statt der Form ${\displaystyle 6n-1}$ kann man auch sagen die Zahl sei der Form ${\displaystyle 6n'+5}$, denn ${\displaystyle 6n-1=6(n-1)+5=6n'+5.}$

Zahlen der Form ${\displaystyle 6n+2}$ und ${\displaystyle 6n+4}$ sind gerade, also keine Primzahlen. Eine Zahl der Form ${\displaystyle 6n+3}$ ist durch 3 teilbar und deshalb ebenso keine Primzahl. So trivial das Ganze ist, hat es doch eine Auswirkung, zum Beispiel auf Carmichael-Zahlen einer bestimmten Form.

Eine Zahl ${\displaystyle c=p_{1}\cdot p_{2}\cdot p_{3}}$ mit drei Primfaktoren

${\displaystyle p_{1}=p,p_{2}=2p-1}$ und ${\displaystyle p_{3}=3p-2}$

ist eine bestimmte Form der Carmichael-Zahl. Dabei kann die Primzahl ${\displaystyle p}$ nur der Form ${\displaystyle p=6n+1}$ sein, denn für ${\displaystyle p=6n-1}$ gilt

${\displaystyle p_{2}=2p-1=12n-3,}$

eine Zahl teilbar durch 3, und deshalb keine Primzahl. Es gilt also:

${\displaystyle p_{1}=p=6n+1,p_{2}=2p-1=12n+1}$ und ${\displaystyle p_{3}=3p-2=18n+1,}$

und damit ist die Aussage äquivalent mit dem Satz:

Eine Zahl mit den drei Primfaktoren ${\displaystyle 6n+1,12n+1}$ und ${\displaystyle 18n+1}$ ist eine Carmichael-Zahl.

Für eine Primzahl ${\displaystyle p\ }$ gilt: ${\displaystyle p\ }$ teilt ${\displaystyle p \choose m}$ für alle ${\displaystyle m\ }$ mit ${\displaystyle 1\leq m\leq p-1}$. Warum das so ist und warum die Umkehrung (Wenn für eine natürliche Zahl ${\displaystyle n\ }$ gilt, dass ${\displaystyle n\ }$ teilt ${\displaystyle n \choose m}$ für alle ${\displaystyle m\ }$ mit ${\displaystyle 1\leq m\leq n-1}$, dann ist ${\displaystyle n\ }$ eine Primzahl) gilt, lässt sich an der folgenden Überlegung verdeutlichen:

Angenommen man hat eine zusammengesetzte Zahl ${\displaystyle n=p_{1}\cdot p_{2}\cdot ...\cdot p_{n}}$. Als Beispiel nehmen wir die Zahl ${\displaystyle 91=7\cdot 13}$. Mit der ${\displaystyle 91\ }$ betrachten wir zwei Fälle, nämlich ${\displaystyle 91 \choose 7}$ und ${\displaystyle 91 \choose 13}$. Im ersten Fall ist ${\displaystyle {91 \choose 7}={\frac {91\cdot 90\cdot 89\cdot 88\cdot 87\cdot 86\cdot 85}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7}}}$. Wenn wir den Bruch auskürzen wollen, werden wir feststellen, dass von den Zahlen über dem Bruchstrich nur eine einzige Zahl durch ${\displaystyle 7\ }$ teilbar ist, nämlich die ${\displaystyle 91\ }$ selbst. Daraus folgt, dass die Zahl, die den Bruch ${\displaystyle {\frac {91\cdot 90\cdot 89\cdot 88\cdot 87\cdot 86\cdot 85}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7}}}$ repräsentiert, gar nicht durch ${\displaystyle 91\ }$ teilbar sein kann. Das gleiche gilt für ${\displaystyle {91 \choose 13}={\frac {91\cdot 90\cdot 89\cdot 88\cdot 87\cdot 86\cdot 85\cdot 84\cdot 83\cdot 82\cdot 81\cdot 80\cdot 79}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10\cdot 11\cdot 12\cdot 13}}}$. Auch hier ist die einzige Zahl über dem Bruchstrich, die durch ${\displaystyle 13\ }$ teilbar ist, die ${\displaystyle 91\ }$ selbst. Warum ist das so? Weil in einem Produkt aus ${\displaystyle n\ }$ aufeinander folgenden Zahlen genau eine Zahl durch ${\displaystyle n\ }$ teilbar sein muss. Bei einer Primzahl trifft dieser Fall genau für ${\displaystyle p \choose p}$ zu. Aber dieser Binomialkoeffizient spielt für die Eigenschaft von Primzahlen bezüglich der Binomialkoeffizienten gar keine Rolle.

Die folgenden Eigenschaften haben mit dem kleinen fermatschen Satz zu tun und haben zu Primzahltests auf Basis von Wahrscheinlichkeiten geführt. Natürliche Zahlen, die keine Primzahlen sind und diese Tests trotzdem bestehen, also aufgrund dieser Tests fälschlicherweise als Primzahlen angesehen werden könnten, sind fermatsche Pseudoprimzahlen.

Angeblich war chinesischen Mathematikern schon ca. 500 v. Chr. bekannt, dass für jede Primzahl ${\displaystyle p}$ gilt, dass ${\displaystyle p}$ die Zahl ${\displaystyle 2^{p}-2}$ teilt. Sie vermuteten allerdings fälschlicherweise, dass auch die Umkehrung stimmt; dass also, wenn ${\displaystyle n}$ die Zahl ${\displaystyle 2^{n}-2}$ teilt, dieses ${\displaystyle n}$ eine Primzahl sein muss.

Die Verallgemeinerung

Wenn ${\displaystyle p}$ eine Primzahl ist, dann gilt, dass ${\displaystyle p}$ jedes ${\displaystyle a^{p}-a}$ teilt.

ist nach dem Juristen und Amateur-Mathematiker Pierre de Fermat als kleiner fermatscher Satz bekannt geworden. Benutzt wird aber eher folgende Variante:

Wenn ${\displaystyle p}$ eine Primzahl ist, dann gilt ${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$ für jedes zu ${\displaystyle p}$ teilerfremde ${\displaystyle a>1}$.

Der Satz lässt sich einschränken auf: Wenn ${\displaystyle p}$ eine Primzahl ist, dann gilt für alle ${\displaystyle 2\leq a\leq p-2}$ dass ${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$ ist.

Umgekehrt gilt nicht dass eine Zahl ${\displaystyle n}$, wofür ${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$ für jedes zu ${\displaystyle n}$ teilerfremde ${\displaystyle a>1\ }$,unbedingt eine Primzahl ist. Ist ${\displaystyle n}$ keine Primzahl, dann nennt man sie Carmichael-Zahl.

Eine etwas stärke Eigenschaft, die sich auf den kleinen fermatschen Satz zurückführen lässt, ist folgende:

Wenn ${\displaystyle p}$ eine Primzahl ist, so gilt für jede zu ${\displaystyle p}$ teilerfremde natürliche Zahl ${\displaystyle a}$

${\displaystyle (a^{\frac {p-1}{2}}-1)\cdot (a^{\frac {p-1}{2}}+1)=a^{p-1}-1\equiv 0{\pmod {p}}.}$

Es gilt folglich entweder

${\displaystyle a^{\frac {p-1}{2}}\equiv 1{\pmod {p}},}$

oder

${\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}.}$

Diese Folgerung wird Leonhard Euler zugeschrieben.

Es lässt sich beweisen dass im ersten Fall die Zahl ${\displaystyle a}$ modulo ${\displaystyle p}$ ein quadratischer Rest ist, und im zweiten Fall ein quadratischer Nichtrest. Es gilt also die Kongruenz:

${\displaystyle a^{\frac {p-1}{2}}\equiv \left({\frac {a}{p}}\right){\pmod {p}}}$.

Dabei ist

${\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}1&{\mbox{wenn }}a{\mbox{ quadratischer Rest modulo }}p{\mbox{ ist}}\\-1&{\mbox{wenn }}a{\mbox{ quadratischer Nichtrest modulo }}p{\mbox{ ist}}\\0&{\mbox{wenn }}a{\mbox{ ein Vielfaches von }}p{\mbox{ ist}}\end{cases}}}$

das Legendre-Symbol, ein Spezialfall des Jacobi-Symbols, das die gleiche Schreibweise hat, und für Primzahlen p übereinstimmen.

Der Beweis stützt auf der Ergebnisse:

• Es gibt modulo p genau (p-1)/2 Quadratreste.
• Die Gleichung ${\displaystyle a^{\frac {p-1}{2}}-1\equiv 0{\pmod {p}}}$ hat nicht mehr als (p-1)/2 Lösungen.

Wenn a ein Quadratrest modulo p ist, gilt ${\displaystyle a\equiv x^{2}{\pmod {p}}}$, also

${\displaystyle a^{\frac {p-1}{2}}\equiv x^{p-1}\equiv 1{\pmod {p}}.}$

Es sind also genau die (p-1)/2 Quadratreste wofür gilt ${\displaystyle a^{\frac {p-1}{2}}\equiv 1{\pmod {p}}.}$ Fuer die restliche Zahlen a, die quadratische Nichtreste, gilt:

${\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}.}$

Ein Beispiel: 7 ist die Primzahl ${\displaystyle p\ }$, 2 ist die Basis ${\displaystyle a_{1}\ }$ und 5 die Basis ${\displaystyle a_{2}\ }$.

Es gilt: ${\displaystyle 2^{\frac {7-1}{2}}\equiv 1\mod 7}$, da Quadratzahlen der Form ${\displaystyle 7n+2}$ existieren. Es gilt: ${\displaystyle 5^{\frac {7-1}{2}}\equiv -1\mod 7}$, da keine Quadratzahlen der Form ${\displaystyle 7n+5}$ existieren.

Dass aus ${\displaystyle a^{\frac {p-1}{2}}\equiv 1\mod p}$ bzw. ${\displaystyle a^{\frac {p-1}{2}}\equiv -1\mod p}$ folgt, dass ${\displaystyle a^{p-1}\equiv 1\mod p}$ gilt, läßt sich daraus ersehen, dass

${\displaystyle \left(a^{\frac {p-1}{2}}\right)^{2}=a^{2\cdot {\frac {p-1}{2}}}=a^{p-1}}$ und ${\displaystyle 1\cdot 1=(-1)\cdot (-1)=1}$ ist.

Für positive natuerliche Zahlen m und n und die Primzahl p gilt:

${\displaystyle {\binom {m}{n}}\equiv \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}}.}$

Darin sind:

${\displaystyle m=m_{k}p^{k}+m_{k-1}p^{k-1}+\cdots +m_{1}p+m_{0},}$

und

${\displaystyle n=n_{k}p^{k}+n_{k-1}p^{k-1}+\cdots +n_{1}p+n_{0}}$

die Entwicklungen von m und n mit Beziehung zur Basis p.

Der Satz von Wilson besagt, dass eine natürliche Zahl n > 1 dann und nur dann eine Primzahl ist, wenn

${\displaystyle (n-1)!\ \equiv -1{\pmod {n}}.}$

Daraus folgt

${\displaystyle (n-2)!\ \equiv 1{\pmod {n}}.}$

Die Perrin-Folge (benannt nach dem Mathematiker R.Perrin) ist wie folgt definiert:

${\displaystyle P_{0}=3}$

${\displaystyle P_{1}=0}$

${\displaystyle P_{2}=2}$

${\displaystyle P_{n}=P_{n-2}+P_{n-3}}$

Für die Perrin-Folge gilt nun, wenn ${\displaystyle p}$ eine Primzahl ist, dass ${\displaystyle P_{p}}$ durch p teilbar ist.

Die allgemeinen Lucas-Folgen ${\displaystyle U_{n}(P,Q)}$ und ${\displaystyle V_{n}(P,Q)}$ sind nach dem französischen Mathematiker Édouard Lucas benannt, der sich als erster mit ihnen beschäftigt hat.

Die allgemeine Lucas-Folge ${\displaystyle V_{n}(P,Q)}$ ist definiert als diejenigen Folge, wofür

${\displaystyle V_{0}(P,Q)=2,\quad V_{1}(P,Q)=P}$

und die für n > 1 den Rekursionsformel

${\displaystyle V_{n}(P,Q)=P\cdot V_{n-1}(P,Q)-Q\cdot V_{n-2}(P,Q)}$

genügt.

Für die Lucasfolge ${\displaystyle V_{n}(P,Q)}$ gilt, wenn ${\displaystyle p}$ eine Primzahl ist, dass ${\displaystyle V_{p}(P,Q)-P}$ durch p teilbar ist.

Die allgemeine Lucas-Folge ${\displaystyle U_{n}(P,Q)}$ ist definiert als diejenige Folge, wofür

${\displaystyle U_{0}(P,Q)=0,\quad U_{1}(P,Q)=1}$

und die für n > 1 den Rekursionsformel

${\displaystyle U_{n}(P,Q)=P\cdot U_{n-1}(P,Q)-Q\cdot U_{n-2}(P,Q)}$

genügt.