zum Directory-modus

Teilbarkeit

Primzahlen

Primzahl
Eine positive ganze Zahl p heißt Primzahl, falls sie nur triviale Teiler besitzt.

Die trivialen Teiler für eine positive ganze Zahl n sind 1 und | n | . Die Teiler von 13 sind 1 und 13 , d.h. nur triviale Teiler und somit ist 13 eine Primzahl. Die Teiler von 20 sind 1 , 2 , 4 , 5 , 10 , 20 und folglich ist 20 keine Primzahl.

Die Folge von Primzahlen fängt wie folgt an

2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , .

Laut einem Satz von Euklid gibt es unendlich viele Primzahlen. Es ist eine Definitionssache, ob die 1 als Primzahl gilt. Heutzutage setzt man die erste Primzahl gleich 2 . Die 2 ist übrigens die einzige gerade Primzahl, da eine gerade Zahl > 2 immer durch 2 teilbar ist und folglich keine Primzahl sein kann.

Theorem
Jede natürliche Zahl n ist Produkt endlich vieler Primzahlen
n = p 1 e 1 p 2 e 2 p 3 e 3 p m e m = i = 1 m p i e i ,
wobei p 1 , p 2 , , p m verschiedene Primzahlen und e 1 , e 2 , , e m natürliche Zahlen sind.

Eine solche Faktorisierung wird als Primfaktorenzerlegung bezeichnet und sie ist eindeutig, z.B.

12 = 2 2 3 1 , 14 = 2 1 7 1 , 18 = 2 1 3 2 , 132 = 2 2 3 1 11 1 .

Es gibt keinen bekannten effizienten Algorithmus zur Primfaktorenzerlegung und deswegen sind Primzahlen wichtig für die Verschlüsselung von Informationen. Dazu werden Schlüssel verwendet, die man aus dem Produkt zweier Primzahlen erhält. Kennt man die beiden Primzahlen nicht, ist es nur mit erheblichem Rechenaufwand möglich, die Schlüsselzahl in ihre Faktoren zu zerlegen, mit den Primzahlen dagegen ist dies nur eine kleine Angelegenheit. Wichtig sind Primzahlen auch für die Erzeugung von Zufallszahlen.

Seite 2 von 2>