Primzahlen: I. Kapitel: Die Eigenschaften der Primzahl

Primzahlen

Einleitung

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.

Primzahlen der Form 4n+1 und 4n-1

Außer 2 ist jede Primzahl ungerade und hat deshalb die Form $4n+1$ oder $4n-1$. Auf äquivalente Weise könnte man sagen eine ungerade Zahl hat die Form $4n+1$ oder $4n+3$, denn $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 $4n-1\$ besitzt, muss sie eine ungerade Anzahl an Primfaktoren der Form $4p-1\$ besitzen, also mindestens einen Primfaktor dieser Form.

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

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

Das Produkt zweier Zahlen der Form $4n-1$ hat die Form $4n+1$

$(4n-1)(4m-1)=16nm-4(n+m)+1=4(4nm-n-m)+1=4k+1$

Das Produkt zweier Zahlen der Form $4n+1$ hat die Form $4n+1$

$(4n+1)(4m+1)=16nm+4(n+m)+1=4(4nm+n+m)+1=4k'+1$

Das Produkt einer Zahl der Form $4n-1$ und einer Zahl der Form $4n+1$ hat die Form $4n-1$

$(4n-1)(4m+1)=16nm+4(n-m)-1=4(4nm+n-m)-1=4k''-1$

Primzahlen der Form 6n+1 und 6n-1

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

Zahlen der Form $6n+2$ und $6n+4$ sind gerade, also keine Primzahlen. Eine Zahl der Form $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 $c=p_{1}\cdot p_{2}\cdot p_{3}$ mit drei Primfaktoren

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

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

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

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

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

und damit ist die Aussage äquivalent mit dem Satz:

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

Binomialkoeffizient

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

Angenommen man hat eine zusammengesetzte Zahl $n=p_{1}\cdot p_{2}\cdot ...\cdot p_{n}$. Als Beispiel nehmen wir die Zahl $91=7\cdot 13$. Mit der $91\$ betrachten wir zwei Fälle, nämlich $91 \choose 7$ und $91 \choose 13$. Im ersten Fall ist ${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 $7\$ teilbar ist, nämlich die $91\$ selbst. Daraus folgt, dass die Zahl, die den Bruch ${\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 $91\$ teilbar sein kann. Das gleiche gilt für ${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 $13\$ teilbar ist, die $91\$ selbst. Warum ist das so? Weil in einem Produkt aus $n\$ aufeinander folgenden Zahlen genau eine Zahl durch $n\$ teilbar sein muss. Bei einer Primzahl trifft dieser Fall genau für $p \choose p$ zu. Aber dieser Binomialkoeffizient spielt für die Eigenschaft von Primzahlen bezüglich der Binomialkoeffizienten gar keine Rolle.

Der kleine Fermat

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.

Der kleine Fermatsche Satz

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

Die Verallgemeinerung

Wenn $p$ eine Primzahl ist, dann gilt, dass $p$ jedes $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 $p$ eine Primzahl ist, dann gilt $a^{p-1}\equiv 1{\pmod {p}}$ für jedes zu $p$ teilerfremde $a>1$.

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

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

Euler

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

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

$(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

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

oder

$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 $a$ modulo $p$ ein quadratischer Rest ist, und im zweiten Fall ein quadratischer Nichtrest. Es gilt also die Kongruenz:

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

Dabei ist

$\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 $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 $a\equiv x^{2}{\pmod {p}}$, also

$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 $a^{\frac {p-1}{2}}\equiv 1{\pmod {p}}.$ Fuer die restliche Zahlen a, die quadratische Nichtreste, gilt:

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

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

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

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

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

Lucas-Theorem

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

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

Darin sind:

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

und

$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.

Wilson

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

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

Daraus folgt

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

Lineare Rekursionen

Perrin-Folge

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

$P_{0}=3$

$P_{1}=0$

$P_{2}=2$

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

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

Die Lucas-Folge V_n (P,Q)

Die allgemeinen Lucas-Folgen $U_{n}(P,Q)$ und $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 $V_{n}(P,Q)$ ist definiert als diejenigen Folge, wofür

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

und die für n > 1 den Rekursionsformel

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

genügt.

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

Die Lucas-Folge U_n (P,Q)

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

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

und die für n > 1 den Rekursionsformel

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

genügt.