Mathe 1 Primzahlen

Seien m, n ∈ ℕ. Wir nennen m und n teilerfremd, wenn die Primfaktorzerlegungen von m und n keinen gemeinsamen Faktor haben.

a) 2 · 2 · 2 · 3 = 24

b) 2 · 2 · 5 · 5 = 100

a) nein

b) ja

Ja, 79 ist eine Primzahl. Wie Sie sehen, ist es für „größere“ Zahlen gar nicht mehr so leicht zu entscheiden, ob es sich um eine Primzahl handelt.

Sieb des Eratosthenes,

Fermat-Test

Bei diesem Verfahren, dem Sieb des Eratosthenes, handelt es sich streng genommen nicht um einen Test. Vielmehr dient das Verfahren dazu, alle Primzahlen bis zu einem bestimmten Grenzwert zu bestimmen.

Man wählt einen Maximalwert n ∈ ℕ mit n ≥ 2 und notiert alle Zahlen 2, 3, 4, ..., n in einer Liste. Jede Zahl erhält eine Markierung, die anzeigt, ob es sich um eine Primzahl oder um eine zusammengesetzte Zahl handelt. Zunächst sind alle Zahlen unmarkiert und somit potenzielle Primzahlen. Das Verfahren läuft nun iterativ wie folgt:

1. Die kleinste unmarkierte Zahl pi wird als Primzahl markiert.

2. Danach werden alle Vielfachen von pi als zusammengesetzte Zahlen markiert. Man beginnt dabei mit dem Quadrat von pi , weil alle kleineren Vielfachen bereits Vielfache von Zahlen < pi sind und deshalb bereits als zusammengesetzte Zahlen markiert wurden.

3. Falls das Quadrat von pi größer ist als der gewählte Maximalwert n, sind alle zusammengesetzten Zahlen ≤ n bereits als solche markiert (denn sie sind Vielfache von Zahlen < pi ) und das Verfahren bricht ab. Alle noch unmarkierten Zahlen sind Primzahlen und werden entsprechend markiert.

Der Fermat-Test ist auch für sehr große Zahlen geeignet und kommt in der Praxis bei Kryptoverfahren tatsächlich zum Einsatz. Es handelt sich – wie übrigens bei den meisten effizienten Primzahltests – um einen sogenannten probabilistischen Test. Das bedeutet, wenn die betrachtete Zahl den Test nicht besteht, so ist sie mit Sicherheit aus Faktoren zusammengesetzt (die Faktoren werden dabei allerdings nicht bestimmt).

Andernfalls handelt es sich mit einer gewissen Wahrscheinlichkeit um eine Primzahl. Indem man den Test mehrmals durchführt, kann man die Wahrscheinlichkeit, dass die betrachtete Zahl wirklich eine Primzahl ist, entsprechend maximieren.

Die folgenden Zahlen sind Primzahlen: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

Nein, definitionsgemäß ist 1 keine Primzahl.