Gegeneinander Primzahlen. Grundlagen

Lehrbücher der Mathematik sind manchmal schwer zu verstehen. Die trockene und klare Sprache der Autoren steht nicht immer zum Verständnis zur Verfügung. Und die Themen dort sind immer miteinander verbunden, wechselseitig fließend. Um ein Thema zu meistern, müssen Sie eine Reihe von Vorträgen aufstellen und manchmal sogar das gesamte Lehrbuch durchblättern. Ist es schwierig? Ja. Und wagen wir es, diese Schwierigkeiten zu umgehen und versuchen, das Thema nicht ganz Standardansatz zu finden. Machen wir einen Exkurs ins Land der Zahlen. Definition, aber wir lassen immer noch dasselbe, weil die Regeln der Mathematik nicht abgebrochen werden können. Also, relativ Primzahlen sind natürliche Zahlen, mit einem gemeinsamen Teiler gleich eins. Das ist klar? Komplett.

Für ein illustrativeres Beispiel nehmen wirNummern 6 und 13. Beide sind durch eins teilbar (relativ prim). Aber die Zahlen 12 und 14 können nicht so sein, weil sie nicht nur in 1, sondern auch in 2 geteilt sind. Die folgenden Zahlen - 21 und 47 passen auch nicht in die Kategorie "wechselseitig Primzahlen": sie können nicht nur durch 1 geteilt werden, sondern auch am 7.

Bezeichnen Sie einander Primzahlen als (a, y) = 1.

Es kann sogar einfacher gesagt werden: Der gemeinsame Teiler (der größte) ist hier gleich eins.
Warum brauchen wir solches Wissen? Es gibt genug Gründe.

Gegenseitige Primzahlen sind in einigen enthaltenVerschlüsselungssystem. Diejenigen, die mit den Chiffren von Hill oder mit dem System der Permutationen von Caesar arbeiten, verstehen: ohne dieses Wissen - überall. Wenn Sie von Generatoren von Pseudozufallszahlen gehört haben, werden Sie es wahrscheinlich nicht wagen zu leugnen, dass dort auch relativ Primzahlen verwendet werden.

Jetzt reden wir über Möglichkeiten, solche Zahlen zu bekommen. Die einfachen Zahlen können, wie Sie verstehen, nur zwei Teiler haben: Sie sind durch sich und durch eins teilbar. Zum Beispiel sind 11, 7, 5, 3 einfache Zahlen, aber 9 ist nicht, weil diese Zahl bereits durch 9 teilbar ist, und durch 3 und durch 1.

Und wenn a - Die Nummer ist Primzahl, und die - aus der Menge {1, 2, ... a - 1}, dann ist es garantiert (a, die) = 1 oder relativ Primzahlen - a und die.

Dies ist nicht einmal eine Erklärung, sondern eine Wiederholung oder Zusammenfassung des eben Gesagten.

Primzahlen zu bekommen ist wahrscheinlich ein SiebEratosthenes jedoch, für beeindruckende Zahlen (Milliarden zum Beispiel) ist diese Methode zu lang, aber im Gegensatz zu Super-Formeln, die manchmal falsch, zuverlässiger sind.

Sie können nach Auswahl arbeiten die > a. Dazu wird y so gewählt, dass die Zahl an ist a nicht geteilt. Dazu wird die Zahl einfach mit einer natürlichen Zahl multipliziert und die Menge addiert (oder im Gegenteil abgezogen) (z. B. p), die weniger ist a:

y = pa + k

Wenn zum Beispiel a = 71, p = 3, q ​​= 10, dann jeweils die hier wird es gleich 713 sein. Eine andere Auswahl mit Grad ist ebenfalls möglich.

Zusammengesetzte Zahlen sind, im Gegensatz zu einfachen, in sich selbst und in 1 und in andere Zahlen (auch ohne Rest) unterteilt.

Mit anderen Worten, natürliche Zahlen (außer einer) sind in zusammengesetzte und einfache Zahlen unterteilt.

Einfache Zahlen sind natürliche Zahlen, die nicht enthalten sindnichttriviale (andere als die Zahl selbst und eine) Teiler. Besonders wichtig ist ihre Rolle in der modernen, sich schnell entwickelnden Kryptographie, dank der die Zahlenlehre, die bisher als eine Disziplin des Abstrakten galt, so gefragt ist: Datenschutzalgorithmen werden ständig verbessert.

Die größte Primzahl gefundenArzt-Augenarzt Martin Novak, die an dem Projekt teilgenommen GIMPS (distributive Computing) zusammen mit anderen Enthusiasten, die etwa 15 Tausend gezählt. In den Berechnungen dauerte sechs Jahre lang. Es waren zweieinhalb Dutzend Computer in der Augenklinik von Nowak. Das Ergebnis der titanischen Arbeit und Beharrlichkeit war die Zahl 225964951-1, mit dem Schreiben in 7816230 Dezimalstellen. Übrigens wurde der Rekord der größten Anzahl sechs Monate vor dieser Eröffnung vergeben. Und die Zeichen dort waren eine halbe Million weniger.

Ein Genie, das eine Nummer nennen will, woDie Länge der Dezimal-Rekord "wird" zehnmillionste Marke springen, gibt es eine Chance, nicht nur Weltruhm, sondern auch 100 000 Dollar zu bekommen. Übrigens erhielt Nyan Hiratwal einen kleineren Betrag (50.000 $) für die Zahl, die die millionste Zeichenreihe überwindet.