Primzahlen: I. Kapitel: Die Eigenschaften der Primzahl

Aus Wikibooks

Einleitung[Bearbeiten]

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[Bearbeiten]

Außer 2 ist jede Primzahl ungerade und hat deshalb die Form oder . Auf äquivalente Weise könnte man sagen eine ungerade Zahl hat die Form oder , denn . Die beiden möglichen Formen spielen eine unterschiedliche Rolle bei ungeraden, zusammengesetzten natürlichen Zahlen.

Wenn eine solche Zahl die Form besitzt, muss sie eine ungerade Anzahl an Primfaktoren der Form besitzen, also mindestens einen Primfaktor dieser Form.
Eine ungerade natürliche Zahl der Form wiederum hat entweder keine Primfaktoren der Form oder ihre Anzahl ist gerade.
Das lässt sich über folgende Sätze zeigen:
Das Produkt zweier Zahlen der Form hat die Form
Das Produkt zweier Zahlen der Form hat die Form
Das Produkt einer Zahl der Form und einer Zahl der Form hat die Form

Primzahlen der Form 6n+1 und 6n-1[Bearbeiten]

Primzahlen, die größer als drei sind, haben entweder die Form oder . Statt der Form kann man auch sagen die Zahl sei der Form , denn

Zahlen der Form und sind gerade, also keine Primzahlen. Eine Zahl der Form 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 mit drei Primfaktoren
und
ist eine bestimmte Form der Carmichael-Zahl. Dabei kann die Primzahl nur der Form sein, denn für gilt
eine Zahl teilbar durch 3, und deshalb keine Primzahl. Es gilt also:
und
und damit ist die Aussage äquivalent mit dem Satz:
Eine Zahl mit den drei Primfaktoren und ist eine Carmichael-Zahl.


Binomialkoeffizient[Bearbeiten]

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

Angenommen man hat eine zusammengesetzte Zahl . Als Beispiel nehmen wir die Zahl . Mit der betrachten wir zwei Fälle, nämlich und . Im ersten Fall ist . Wenn wir den Bruch auskürzen wollen, werden wir feststellen, dass von den Zahlen über dem Bruchstrich nur eine einzige Zahl durch teilbar ist, nämlich die selbst. Daraus folgt, dass die Zahl, die den Bruch repräsentiert, gar nicht durch teilbar sein kann. Das gleiche gilt für . Auch hier ist die einzige Zahl über dem Bruchstrich, die durch teilbar ist, die selbst. Warum ist das so? Weil in einem Produkt aus aufeinander folgenden Zahlen genau eine Zahl durch teilbar sein muss. Bei einer Primzahl trifft dieser Fall genau für zu. Aber dieser Binomialkoeffizient spielt für die Eigenschaft von Primzahlen bezüglich der Binomialkoeffizienten gar keine Rolle.

Babbage und Wolstenholme[Bearbeiten]

Der kleine Fermat[Bearbeiten]

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[Bearbeiten]

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

Die Verallgemeinerung

Wenn eine Primzahl ist, dann gilt, dass jedes teilt.

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

Wenn eine Primzahl ist, dann gilt für jedes zu teilerfremde .

Der Satz lässt sich einschränken auf: Wenn eine Primzahl ist, dann gilt für alle dass ist.

Umgekehrt gilt nicht dass eine Zahl , wofür für jedes zu teilerfremde ,unbedingt eine Primzahl ist. Ist keine Primzahl, dann nennt man sie Carmichael-Zahl.

Euler[Bearbeiten]

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

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

Es gilt folglich entweder

oder

Diese Folgerung wird Leonhard Euler zugeschrieben.

Es lässt sich beweisen dass im ersten Fall die Zahl modulo ein quadratischer Rest ist, und im zweiten Fall ein quadratischer Nichtrest. Es gilt also die Kongruenz:

.

Dabei ist

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 hat nicht mehr als (p-1)/2 Lösungen.

Wenn a ein Quadratrest modulo p ist, gilt , also

Es sind also genau die (p-1)/2 Quadratreste wofür gilt Fuer die restliche Zahlen a, die quadratische Nichtreste, gilt:


Ein Beispiel: 7 ist die Primzahl , 2 ist die Basis und 5 die Basis .

Es gilt: , da Quadratzahlen der Form existieren. Es gilt: , da keine Quadratzahlen der Form existieren.

Dass aus bzw. folgt, dass gilt, läßt sich daraus ersehen, dass

und ist.

Miller-Rabin[Bearbeiten]

Lucas-Theorem[Bearbeiten]

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

Darin sind:

und

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

Wilson[Bearbeiten]

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

Daraus folgt

Giuga[Bearbeiten]

Lineare Rekursionen[Bearbeiten]

Perrin-Folge[Bearbeiten]

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

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

Die Lucas-Folge Vn (P,Q)[Bearbeiten]

Die allgemeinen Lucas-Folgen und sind nach dem französischen Mathematiker Édouard Lucas benannt, der sich als erster mit ihnen beschäftigt hat.

Die allgemeine Lucas-Folge ist definiert als diejenigen Folge, wofür

und die für n > 1 den Rekursionsformel

genügt.

Für die Lucasfolge gilt, wenn eine Primzahl ist, dass durch p teilbar ist.

Die Lucas-Folge Un (P,Q)[Bearbeiten]

Die allgemeine Lucas-Folge ist definiert als diejenige Folge, wofür

und die für n > 1 den Rekursionsformel

genügt.