Warum beim Primzahlentest nur bis zur Wurzel testen?
Wir haben im Unterricht durchgesprochen wie man testen kann, ob eine Zahl prim ist oder nicht. Ich verstehe grundsätzlich wie man das macht und hab auch gut nachvollziehen können, warum man nicht weiter testen muss als bis zur Hälfte der Zahl.
Dann wurde aber gesagt, dass man eigentlich sogar nur bis zur Wurzel der Zahl testen muss, weil sich danach alles wiederholt - Kann mir das jemand erklären? Ich hab da irgendwie kein Bild vor Augen warum das so sein soll.. :(
4 Antworten
Sei t ein Teiler von a, wobei t > √a
Dann ist n = a/t eine natürliche Zahl, und n ist wegen
n = a/t ⇔ n t = a ⇔ t = a/n (gilt für alle für t, n ≠ 0)
ebenfalls ein Teiler von a. - Wegen
t > √a > 0
gilt , weil der Übergang zum Kehrwert für positive Zahlen das Ungleichheitszeichen umkehrt:
1 / t < 1 / √a ; | * a > 0 (Ungleichheitszeichen bleibt erhalten)
a / t < a / √ a;
also insgesamt:
n = a / t < a / √a = √a.
Ergebnis:
- Zu jedem Teiler t > √a von a gehört eine Teiler n < √a.
- Wenn du alle n kennst, dann auch alle t.
Wenn eine Zahl keine Primzahl ist, ist sie durch mindestens 2 Zahlen ohne Rest teilbar
Für Zahlen größer als die Wurzel muß der Partner kleiner als die Wurzel sein - die Zahl hat man aber schon vorher getestet
Eine Zahl, die nicht prim ist, muss aus mindestens 2 Primfaktoren bestehen. Der kleinere davon ist immer kleiner oder gleich der Wurzel der Ausgangszahl.
21 = 3 · 7
25 = 5 · 5
26 = 13 · 2
Lässt sich kein Primfaktor finden, der kleiner oder gleich der Wurzel der Ausgangszahl ist, dann muss diese eine Primzahl sein.
Hilft dir dieses Beispiel hier?