- Eigenschaften von Primzahlen
- Wie man weiß, ob eine Zahl eine Primzahl ist
- Möglichkeiten, eine Primzahl zu finden
- Eulers Formel
- Das Sieb von Eratosthenes
- Übungen
- - Übung 1
- Lösung
- - Übung 2
- Lösung für
- Lösung b
- Verweise
Die Primzahlen , auch Primzahl absolut genannt, sind jene natürlichen Zahlen, die nur durch sich selbst und 1 teilbar sind. Diese Kategorienummern sind 2, 3, 5, 7, 11, 13, 17, 19, 23 und viele Plus.
Stattdessen ist eine zusammengesetzte Zahl durch sich selbst, durch 1 und mindestens eine andere Zahl teilbar. Wir haben zum Beispiel 12, das durch 1, 2, 4, 6 und 12 teilbar ist. Konventionell ist 1 nicht in der Liste der Primzahlen oder in der Liste der Verbindungen enthalten.
Abbildung 1. Einige Primzahlen. Quelle: Wikimedia Commons.
Die Kenntnis der Primzahlen reicht bis in die Antike zurück; Die alten Ägypter haben sie bereits benutzt und sie waren sicherlich schon lange vorher bekannt.
Diese Zahlen sind sehr wichtig, da jede natürliche Zahl durch das Produkt von Primzahlen dargestellt werden kann, wobei diese Darstellung eindeutig ist, außer in der Reihenfolge der Faktoren.
Diese Tatsache ist vollständig in einem Satz begründet, der als Grundsatz der Arithmetik bezeichnet wird und besagt, dass Zahlen, die keine Primzahlen sind, notwendigerweise aus Produkten von Zahlen bestehen, die Primzahlen sind.
Eigenschaften von Primzahlen
Hier sind die Hauptmerkmale von Primzahlen:
- Sie sind unendlich, denn egal wie groß eine Primzahl ist, Sie können immer eine größere finden.
-Wenn eine Primzahl p eine andere Zahl a nicht genau teilt, heißt es, dass p und a Primzahlen zueinander sind. In diesem Fall ist der einzige gemeinsame Teiler, den beide haben, 1.
Es ist nicht notwendig, dass a eine absolute Primzahl ist. Zum Beispiel ist 5 eine Primzahl, und obwohl 12 keine Primzahl ist, sind beide Zahlen Primzahlen zueinander, da beide 1 als gemeinsamen Teiler haben.
-Wenn eine Primzahl p eine Potenz der Zahl n teilt, teilt sie auch n. Betrachten wir 100, was einer Potenz von 10 entspricht, insbesondere 10 2 . Es kommt vor, dass 2 sowohl 100 als auch 10 teilt.
-Alle Primzahlen mit Ausnahme von 2 sind ungerade, daher ist ihre letzte Ziffer 1, 3, 7 oder 9. 5 ist nicht enthalten, da es zwar ungerade und Primzahlen ist, aber niemals die endgültige Zahl einer anderen Primzahl ist. Tatsächlich sind alle Zahlen, die mit 5 enden, Vielfache davon und daher keine Primzahlen.
-Wenn p eine Primzahl und ein Teiler des Produkts zweier Zahlen ab ist, teilt p eine davon. Zum Beispiel teilt die Primzahl 3 das Produkt 9 x 11 = 99, da 3 ein Teiler von 9 ist.
Wie man weiß, ob eine Zahl eine Primzahl ist
Primalität ist der Name für die Qualität der Primzahl. Nun, der französische Mathematiker Pierre de Fermat (1601-1665) hat im sogenannten kleinen Theorem von Fermat einen Weg gefunden, die Ursprünglichkeit einer Zahl zu verifizieren:
"Bei einer natürlichen Primzahl p und jeder natürlichen Zahl a größer als 0 ist es wahr, dass ein p - a ein Vielfaches von p ist, solange p eine Primzahl ist."
Wir können dies mit kleinen Zahlen bestätigen, zum Beispiel nehmen wir an, dass p = 4, von dem wir bereits wissen, dass es keine Primzahl ist und bereits = 6:
6 4 - 6 = 1296 - 6 = 1290
Die Zahl 1290 ist nicht genau durch 4 teilbar, daher ist 4 keine Primzahl.
Lassen Sie uns den Test jetzt mit p = 5 machen, was Primzahl und ya = 6 ist:
6 5 - 6 = 7766 - 6 = 7760
7760 ist durch 5 teilbar, da jede Zahl, die mit 0 oder 5 endet, ist. Tatsächlich ist 7760/5 = 1554. Da Fermats kleiner Satz gilt, können wir sicherstellen, dass 5 eine Primzahl ist.
Der Beweis durch den Satz ist effektiv und direkt bei kleinen Zahlen, bei denen die Operation einfach durchzuführen ist. Was tun, wenn wir aufgefordert werden, die Ursprünglichkeit einer großen Zahl herauszufinden?
In diesem Fall wird die Zahl nacheinander auf alle kleineren Primzahlen aufgeteilt, bis eine genaue Teilung gefunden wird oder der Quotient kleiner als der Teiler ist.
Wenn eine Division genau ist, bedeutet dies, dass die Zahl zusammengesetzt ist, und wenn der Quotient kleiner als der Divisor ist, bedeutet dies, dass die Zahl eine Primzahl ist. Wir werden es in gelöster Übung 2 in die Praxis umsetzen.
Möglichkeiten, eine Primzahl zu finden
Es gibt unendlich viele Primzahlen und es gibt keine einzige Formel, um sie zu bestimmen. Betrachten Sie jedoch einige Primzahlen wie diese:
3, 7, 31, 127 …
Es wird beobachtet, dass sie die Form 2 n - 1 haben, mit n = 2, 3, 5, 7, 9 … Wir stellen dies sicher:
2 2 - 1 = 4 - 1 = 3 ; 2 3 - 1 = 8 - 1 = 7 ; 2 5 - 1 = 32 - 1 = 31 ; 2 7 - 1 = 128 - 1 = 127
Wir können jedoch nicht sicherstellen, dass 2 n - 1 im Allgemeinen eine Primzahl ist, da es einige Werte von n gibt, für die es nicht funktioniert, zum Beispiel 4:
2 4 - 1 = 16 - 1 = 15
Und die Zahl 15 ist keine Primzahl, da sie mit 5 endet. Eine der größten bekannten Primzahlen, die durch Computerberechnungen gefunden wurde, hat jedoch die Form 2 n - 1 mit:
n = 57.885.161
Mersennes Formel versichert uns, dass 2 p - 1 immer Primzahl ist, solange p auch Primzahl ist. Zum Beispiel ist 31 Primzahl, so dass es sicher ist, dass 2 31 - 1 auch Primzahl ist :
2 31 - 1 = 2.147.483.647
Mit der Formel können Sie jedoch nur einige Primzahlen bestimmen, nicht alle.
Eulers Formel
Das folgende Polynom ermöglicht das Auffinden von Primzahlen, vorausgesetzt, n liegt zwischen 0 und 39:
P (n) = n 2 + n + 41
Später im Abschnitt über gelöste Übungen gibt es ein Beispiel für seine Verwendung.
Das Sieb von Eratosthenes
Eratosthenes war ein Physiker und Mathematiker aus dem antiken Griechenland, der im 3. Jahrhundert v. Chr. Lebte. Er entwickelte eine grafische Methode, um die Primzahlen zu finden, die wir mit kleinen Zahlen in die Praxis umsetzen können. Sie wird Eratosthenes-Sieb genannt (ein Sieb ist wie ein Sieb).
-Die Zahlen werden in einer Tabelle wie der in der Animation gezeigten platziert.
-Die geraden Zahlen werden dann durchgestrichen, mit Ausnahme von 2, von denen wir wissen, dass sie Primzahlen sind. Alle anderen sind Vielfache davon und daher keine Primzahlen.
-Die Vielfachen von 3, 5, 7 und 11 sind ebenfalls markiert, ausgenommen alle, weil wir wissen, dass sie Primzahlen sind.
-Die Vielfachen von 4, 6, 8, 9 und 10 sind bereits markiert, da sie zusammengesetzt sind und daher ein Vielfaches einiger der angegebenen Primzahlen sind.
-Finally sind die Zahlen, die nicht markiert sind, Primzahlen.
Abbildung 2. Animation des Eratosthenes-Siebs. Quelle: Wikimedia Commons.
Übungen
- Übung 1
Verwenden Sie das Euler-Polynom für Primzahlen, um 3 Zahlen größer als 100 zu finden.
Lösung
Dies ist das Polynom, das Euler vorgeschlagen hat, um Primzahlen zu finden, das für Werte von n zwischen 0 und 39 funktioniert.
P (n) = n 2 + n + 41
Durch Versuch und Irrtum wählen wir einen Wert von n, zum Beispiel n = 8:
P (8) = 8 2 + 8 + 41 = 113
Da n = 8 eine Primzahl größer als 100 ergibt, bewerten wir das Polynom für n = 9 und n = 10:
P (9) = 9 2 + 9 + 41 = 131
P (10) = 10 2 + 10 + 41 = 151
- Übung 2
Finden Sie heraus, ob die folgenden Zahlen Primzahlen sind:
a) 13
b) 191
Lösung für
Die 13 ist klein genug, um Fermats kleinen Satz und die Hilfe des Taschenrechners zu verwenden.
Wir verwenden a = 2, damit die Zahlen nicht zu groß sind, obwohl auch a = 3, 4 oder 5 verwendet werden können:
2 13 - 2 = 8190
8190 ist durch 2 teilbar, da es gerade ist, daher ist 13 Primzahl. Der Leser kann dies bestätigen, indem er denselben Test mit a = 3 durchführt.
Lösung b
191 ist zu groß, um es mit dem Satz und einem gemeinsamen Taschenrechner zu beweisen, aber wir können die Trennung zwischen jeder Primzahl finden. Wir lassen die Division durch 2 weg, weil 191 nicht gerade ist und die Division nicht genau ist oder der Quotient kleiner als 2 ist.
Wir versuchen durch 3 zu teilen:
191/3 = 63.666 …
Und es gibt weder genau noch ist der Quotient kleiner als der Divisor (63.666… ist größer als 3)
Wir versuchen also weiterhin, 191 zwischen den Primzahlen 5, 7, 11, 13 zu teilen, und weder die genaue Teilung wird erreicht, noch der Quotient kleiner als der Teiler. Bis es durch 17 geteilt wird:
191/17 = 11, 2352 …
Da es nicht genau ist und 11.2352… kleiner als 17 ist, ist die Zahl 191 eine Primzahl.
Verweise
- Baldor, A. 1986. Arithmetik. Codex für Editionen und Distributionen.
- Prieto, C. Die Primzahlen. Wiederhergestellt von: paginas.matem.unam.mx.
- Eigenschaften von Primzahlen. Wiederhergestellt von: mae.ufl.edu.
- Smartick. Primzahlen: wie man sie mit dem Eratosthenes-Sieb findet. Wiederhergestellt von: smartick.es.
- Wikipedia. Primzahl. Wiederhergestellt von: es.wikipedia.org.