Primzahl-Aufgabe
-
Man kann zeigen, dass fuer jede Primzahl p>3 gilt: p² % 24 = 1 (man verwendet dabei, dass fuer p>3 prim gilt es ex. k mit p = 6k +/-1). Der Test liefert also eine notwendige Bedingung fuer primheit.
Dummerweise wird auch jede Zahl, deren Primfaktoren alle > 3 sind als ergbnis der modulo rechnung 1 haben.
-
Hallo,
ich hab das auch bis 1000 geprüft und es zeigt definitiv ALLE Primzahlen mit anderen Zahlen an. Gibt es wirklich keine Möglichkeit, diese nicht-Primzahlen auszuschließen? Und asmodis: Kannst du mir einen Beweis für das p = 6k /-1 geben? Denn das scheint zu stimmen, nur ich weiß nicht warum.
MFG Toddy
-
Toddy, 6k +/-1 liefert dir nicht zwingend ein Primzahlenpaar (k=4).
-
Toddy schrieb:
Kannst du mir einen Beweis für das p = 6k /-1 geben? Denn das scheint zu stimmen, nur ich weiß nicht warum.
Das ist nicht schwer.
Jede Zahl ist von einer der folgenden 6 Formen:
6k => geht nicht, ist durch 6 teilbar
6k+1 => möglich
6k+2 => geht nicht, ist durch 2 teilbar
6k+3 => geht nicht, ist durch 3 teilbar
6k+4 => geht nicht, ist durch 2 teilbar
6k+5 (=6(k+1)-1) => möglich
-
D-U-D-E schrieb:
Toddy, 6k +/-1 liefert dir nicht zwingend ein Primzahlenpaar (k=4).
Das nicht, aber jede Primzahl über 3 ist entweder als 6k-1 oder als 6k+1 darstellbar.