Warum ist eine Zahl n eine Primzahl, wenn jede Primzahl <= Wurzel(n) die Zahl nicht teilt?

Question

Aufgabe:

"Willst du also herausfinden, ob eine Zahl eine Primzahl ist oder nicht, reicht es aus, die Teilbarkeit durch alle kleineren Primzahlen zu prüfen."

Satz: Eine natürliche Zahl (n > 1) ist genau dann eine Primzahl, wenn jede Primzahl p ≤ √n die Zahl n nicht teilt.

Problem/Ansatz:

Warum gilt das?

Wenn n KEINE Primzahl, dann kann ich n ja darstellen als Produkt

n = a * b (ein Faktor ist hierbei immer ≤ √n)

Ich muss also theoretisch nur alle Teiler ≤ √n betrachten. Wenn ich keinen finde, dann ist n im Umkehrschluss eine Primzahl.

Wieso ist es jedoch auch ausreichend nur Teiler ≤ √n zu betrachten die Primzahlen sind? Das leuchtet mir nicht ein...

Man könnte sich die Frage ja auch umgedreht stellen. Also jede Zahl n die eine Primzahl ist, lässt sich als Produkt darstellen, bei dem ein Faktor eine Primzahl p ≤ √n ist

Comments

Also jede Zahl n die eine Primzahl ist, lässt sich als Produkt darstellen, bei dem ein Faktor eine Primzahl p ≤ √n ist

Das ist falsch. Meinst du "jede Zahl n die keine Primzahl ist"?

Dann ist es richtig.

---

Ja, richtig :-) Ich meine jede Zahl n die KEINE Primzahl ist. Da war ich etwas unpräzise

---

Hast du es denn jetzt verstanden?

Answer 1

Nimm als Beispiele 36 und 37.

36=6*6

Jede andere Darstellung von 36 als Produkt zweier natürlicher Zahlen besteht aus einer Zahl, die kleiner als 6 ist, und einer, die größer als 6 ist. Um alle Teiler zu finden, müssen also nur 1, 2, 3, 4, 5 und 6 untersucht werden.

Für 37 reicht es daher ebenfalls., alle Kandidaten bis 6 zu testen, denn 7*7=49>37.

:-)

Comments

Hallo,

alle Teiler < sind klar, es geht hier aber nur um die Primzahlen. Wieso reicht es aus, die Teilbarkeit durch alle kleineren PRIMZAHLEN (< Wurzel n) zu prüfen?

Um bei deinem Beispiel der 36 zu bleiben müsste ich mir ja nur die 2,3 und 5 anschauen.

---

Das ist ja auch richtig, dass 2; 3 und 5 ausreichen.

Nimm ein Beispiel, bei dem Primfaktoren größer als die Quadratwurzel sind.

Bei 91 reicht es, die Primzahlen bis 9 zu betrachten, also 2; 3; 5 und 7.

91/7=13 → 91=7*13

Die 13 erhältst du dabei automatisch.

:-)

---

Ich habe deine Frage noch einmal genau durchgelesen.

Die Teilbarkeit z.B. durch 4 musst du nicht untersuchen, wenn 2 schon kein Teiler ist. Durch 6 ist unnötig, wenn die Teilbarkeit durch 2 und 3 schon untersucht wurde. So ist es mit allen Zahlen, die keine Primzahlen sind.

Deshalb reichen die Primzahlen.

:-)