Wie kann ich herausfinden, ob es eine Primzahl ist?
Hallo!
Ich habe gerade Schlag den Raaab (mit drei 'a' weil 'Rab' mit zwei 'a' nicht verwendet werden darf) geschaut, da war die Frage ob die Zahl 91 eine Primzahl ist. Aus dem Bauch heruas habe ich nein geraten, und lag recht.
Aber wie kann ich heraus finden ob eine Zahl eine Primzahl, oder keine ist? Da gibts doch ganz einfache Regeln mit der Quersumme usw.
Danke!
LG
11 Antworten
Erstmal gibts ja die gewöhnlichen Primzahltests. :
Eine Zahl ist durch 2 teilbar, wenn sie gerade ist;
Eine Zahl ist durch 3 teilbar, wenn ihre Quersumme durch 3 teilbar ist;
Eine Zahl ist durch 5 teilbar, wenn sie auf 5 oder 0 endet.
Dann gibt es sehr merkwürdige Tests von wegen alternierenden Quersummen, die allerdings in der Regel viel aufwändiger sind als das schnell im Kopf zu überprüfen.
So, nun willst du wissen, ob die Zahl 91 z.B. eine Primzahl ist. Wenn sie keine Primzahl ist, so lässt sie sich durch eine Primzahl teilen. Nun machst du ne grobe Abschätzung, in welchem Bereich "Wurzel aus 91" liegt. Offenbar gilt, dass "Wurzel aus 91" kleiner ist als 10 und größer als 9. Also genügt es zu prüfen, ob 91 durch eine Primzahl teilbar ist, die kleiner ist als 10 (warum, sage ich dir später ^^)
2, 3 und 5 sind ja schnell geprüft mithilfe der obigen Methoden. Bleibt noch 7 und offenbar ist 91 durch 7 teilbar, somit keine Primzahl.
Nehmen wir doch stattdessen einmal die Zahl 97. Wieder ist ihre Wurzel kleiner als 10, also brauchen wir wieder nur 2, 3, 5 und 7 zu überprüfen (denn das sind die einzigen Primzahlen, die kleiner sind als 10).
2, 3 und 5 können wir wieder ausschließen. Zudem ist 91 durch 7 teilbar und da 97-91= 6, ist 97 auch nicht durch 7 teilbar. Also ist 97 eine Primzahl.
Frage 1: Warum muss ich nur Primzahlen testen?
Naja, wenn 97 durch eine nicht-Primzahl teilbar ist, z.b. 9, dann ist sie automatisch durch eine kleinere Primzahl teilbar (in diesem Fall 3). Und für den Primzahl-Beweis brauchen wir ja nur irgendeinen Teiler ungleich 1 und 97.
Frage 2: Warum muss ich keine Primzahlen prüfen, die größer als 10 sind?
Wurzel aus 97 ist kleiner als 10. Angenommen, es gibt keine Primzahl als Teiler, die kleiner ist als 10, aber eine, die größer als 10 ist (und zugleich ungleich 97). Dann lässt sich 97 als Produkt zweier Zahlen a und b schreiben, die beide größer sind als 10. Dann gilt aber: a * b > 10 * 10 > 97, also ist a * b ungleich 97. Das ist ein Widerspruch, somit muss mindestens eine Primzahl kleiner sein als 10.
Es gibt keine ganz einfachen Regeln, vorallem bei größeren Zahlen wird es äußerst schwer.
Du kannst die Teilbarkeit durch 3 und durch 9 mit der Quersumme herausfinden. Für andere Zahlen gibt es auch solche "Tricks". Die Teilbarkeit durch 5 erkennt man, wenn die letzte Ziffer eine 0 oder eine 5 ist usw.
Du kannst schauen, ob die Zahl durch Summen bildbar ist, die die einen Groesten gemeinsamen Teiler haben groesser 1, dann ist es keinen Primzahl. Hier 70+21=91 GGT= 7, die Zahl ist durch 7 und 13 teilbar.
1.Alle geraden Zahlen sind durch 2 teilbar (Dabei hasst du die Hälfte aller Zahlen ausgeschlossen)
2a. Alle Zahlen mit einer Quersumme die durch 3 teilbar ist, kannst du auch durch 3 teilen. 2b. Alle Zahlen mit einer Quersumme die durch 9 teilbar ist, kannst du auch durch 9 teilen.
- Alle Zahlen die auf 5 enden, kannst du durch 5 teilen (jede zehnte Zahl ausgeschlossen)
Primzahl kannst du nur durch 1 und durch sich selbst teilen, das heisst 91 ist keine weil man 91 z.B. mit 13 teilen kann, 7 mal 13 sind 91
Schon klar, das weiß ich. Aber es gibt doch so kleine 'Tests' die ich durchführen kann, ohne mit jeder Zahl dividieren zu müssen...