Primzahlen: I. Kapitel: Die Eigenschaften der Primzahl

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.

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.

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

 

Daraus folgt

 

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.