Primzahlen sind natürliche Zahlen, die genau zwei Teiler haben, nämlich 1 und sich selbst.

Daher zählt die 1 nicht zu den Primzahlen.

Es gibt unendlich viele Primzahlen. Ein System, welche Zahlen Primzahlen sind, wurde bisher noch nicht gefunden.

Man verwendet Primzahlen häufig in der Kryptographie beim Verschlüsseln von Daten.

Die Primzahlen von 1 bis 100

Folgende Zahlen zwischen 1 und 100 sind prim:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 und 97.

       

Fakten über Primzahlen

  • Die 2 ist die einzige gerade Primzahl.

  • Jede natürliche Zahl lässt sich eindeutig als Produkt von Primzahlen schreiben.     (Primfaktorzerlegung)

  • Wenn das Produkt zweier natürlicher Zahlen durch eine Primzahl teilbar ist, dann muss bereits eine der natürlichen Zahlen durch die Primzahl teilbar gewesen sein.

  

Verfahren zur Überprüfung, ob eine Zahl Primzahl ist

Wenn man eine Zahl gegeben hat und überprüfen soll, ob die gegebene Zahl eine Primzahl ist, ist die einfachste Methode zu versuchen sie der Reihe nach durch alle Primzahlen zu teilen.

Man testet also ob die Zahl durch 2 teilbar ist, dann durch 3, durch 5…

Wenn man bis zur Wurzel der gegebenen Zahl alle Primzahlen als Teiler ausgeschlossen hat, dann ist die Zahl  selbst eine Primzahl. Andernfalls nicht.

Natürlich verwendet man aber heute mit Computern auch andere Verfahren.    

   

Primfaktorzerlegung    

Artikel zum Thema

Als Primfaktorzerlegung bezeichnet man die Darstellung einer Zahl als Produkt von Primzahlen. Dazu verwendet man, dass sich jede natürliche Zahl eindeutig als Produkt von Primzahlen darstellen lässt.

                                                 

Unendlichkeit der Primzahlen

Die Anzahl der Primzahlen ist unendlich. Man kann also keine größte Primzahl finden. Es wird immer eine Primzahl geben die größer ist. Den Beweis für diese These hat Euklid schon vor mehr als 2000 Jahren geliefert.

Unendlichkeitsbeweis nach Euklid (hier ausklappen)

Widerspruchsbeweis

Die Argumentation beruht auf einem Widerspruchsbeweis. Man nimmt also an, es gäbe eine größte Primzahl und versucht durch Argumente auf einen Widerspruch zu kommen. Dann muss die Annahme falsch gewesen sein.

Angenommen, es gibt nur endlich viele Primzahlen, und wir können eine vollständige Liste der Primzahlen angeben.

Beispiel

Zum Beispiel nehmen wir an das wir nur die Primzahlen 2, 3, 5 und 7 haben und nicht mehr.


Nun nimmt man alle Primzahlen aus der Liste mal und addiert 1. Die so entstandene Zahl (nennen wie sie %%p%%) ist nun entweder

  1. selbst eine Primzahl oder
  2. hat eine Primfaktorzerlegung aus Faktoren, die größer sind als die bisher angenommene größte Primzahl

Beispiel

  • Annahme:
    %%7%% ist die größte Primzahl. Liste an Primzahlen: %%2,3,5,7%%
    %%p = 2 \cdot 3 \cdot5 \cdot7 + 1 = 2311%% und %%2311%% ist eine Primzahl.
    %%7%% ist also nicht die größte Primzahl.

  • andere Annahme:
    %%13%% ist die größte Primzahl. Liste an Primzahlen: %%2,3,5,7, 11, 13%%
    %%p = 2 \cdot 3 \cdot5 \cdot7 \cdot 11 \cdot 13 + 1 = 30031%%.
    %%30031 = 59 \cdot 509%% und sowohl %%59%% als auch %%509%% sind Primzahlen, die nicht in unserer Liste und größer als %%13%% sind.
    %%13%% ist also nicht die größte Primzahl.


Unsere Zahl %%p%% ist auf jeden Fall größer als alle Zahlen unserer Liste.

Da %%p -1%% ein Produkt aus unserer Liste aus Primzahlen ist, hat %%p%% beim Teilen durch jede dieser Primzahlen den Rest %%1%% und kann daher keine der Primzahlen aus der Liste als Teiler haben.

Daher kann %%p%% nur Primteiler haben, die größer sind als die Primzahlen aus unserer Liste oder selbst eine Primzahl sein, welche größer ist als die angenommene größte Primzahl unserer Liste.

Die Annahme, es gebe nur endlich viele Primzahlen führt also zu einem Widerspruch.

%%\;\;\Rightarrow\;\;%% Es gibt unendlich viele Primzahlen.

 

Kommentieren Kommentare