Primzahl

Mit Primzahl bezeichnet man eine natürliche Zahl, die nur durch "1" oder sich selbst ohne Rest teilbar ist.

Primzahlen sind 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 53, usw.. Die Ziffer "1" gilt nicht als Primzahl.

Die Anzahl der Primzahlen ist unendlich, die Verteilung der Primzahlen unter den natürlichen Zahlen ist unregelmäßig.

Jede natürliche Zahl kann eindeutig als Produkt von Primzahlen dargestellt werden. (Bsp.: 2345 = 5·7·67), was Primfaktorzerlegung genannt wird. Bei der Primfaktorzerlegung geht man gewöhnlich die Primzahlen von unten (d.h. 2, 3, 5, 7...) durch und prüft, ob die zu zerlegende Zahl durch sie ohne Rest teilbar ist. In diesem Fall schreibt man die Primzahl auf, teilt die zu zerlegende Zahl durch die Primzahl und macht mit dem Ergebnis (dem Quotienten) weiter, bis am Schluss nur noch eine Primzahl übrig bleibt.

Sätze über Primzahlen

Sätze von Fermat

• Wenn p eine Primzahl ist und n eine natürliche Zahl, die kein Vielfaches von p ist, dann ist np-1 stets um 1 größer als das nächst kleinere Vielfache von p
• Jede Primzahl p, die sich durch p=4n+1 erzeugen läßt (n Î IN), läßt sich eindeutig als Summe von zwei ganzzahligen Quadraten darstellen (Bsp.: 233=82+132).

Satz von Lagrange

• Jede natürliche Zahl n läßt sich als Summe von höchstens vier Quadraten ganzer Zahlen darstellen.

Satz von Dirichlet

• Wenn ggT(a,b)=1, dann gibt es unendlich viele Primzahlen p der Form p = n·a + b (n Î IN).

Dreiprimzahlsatz

• Jede ungerade natürliche Zahl ³9 ist Summe dreier ungerader Primzahlen.