Verallgemeinerung des Brokar-Problems

Die Geschichte

Hilbert wies 1900 auf dem II. Internationalen Mathematikerkongress in Paris auf die praktische Bedeutung der Zahlentheorie hin. Die Lösung abstrakter Probleme führte häufig zur Entstehung eines neuen mathematischen Apparats. Ein anschauliches Beispiel ist das Great Farm Theorem, bei dessen Nachweis Ende des 20. Jahrhunderts die meromorphen Funktionen untersucht wurden, die moderne Konstrukteure in Automobil- und Flugzeugfabriken sowie von IT-Spezialisten im Rahmen der Simulation verwenden. Die Probleme der "schönen Zahlen" - einfache Zwillinge und perfekte Zahlen, die im antiken Griechenland als nahezu nutzlos galten, bieten der modernen Kryptographie nun stabile Algorithmen zur Schlüsselgenerierung.

Im Jahr 1913 popularisierte Ramanujan die unbestimmte Gleichung:

$$

$$n! + 1 = m ^ 2 (1)$$

Zuvor erschien es in den Werken von Henri Brocard. Historikern zufolge begannen zwei Mathematiker, diese Gleichung unabhängig voneinander zu studieren. Offensichtlich wächst die Fakultät schneller als ein Quadrat, so dass die ersten Lösungen schnell durch erschöpfende Suche nach n erhalten werden können. Wir bekommen:

$$

$$4! = 5 ^ 2-1$$

$$

$$5! = 11 ^ 2-1$$

$$

$$7! = 71 ^ 2-1$$

Im Jahr 2000 wurden die Werte durch Computeraufzählung überprüft $$$n$ vorher $$$10 ^ 9$ und neue Lösungen konnten nicht gefunden werden. Der Artikel schlägt meinen Ansatz zur Überprüfung bestimmter Fälle des Brokar-Problems vor und formuliert auch eine verallgemeinerte Version des mathematischen Problems, deren Lösung es unabhängig von der ABC-Hypothese ermöglicht, Gleichungen der Form zu lösen:

$$

$$n! = P (x)$$

Voraussetzungen

Die modulare Arithmetik ist ein leistungsfähiges Werkzeug für eine vorläufige Bewertung der Komplexität eines Problems und der Zuordnung von Sonderfällen. Zum Beispiel ist es einfach, das für gerade zu zeigen $$$m$ Brokars Problem hat keine Lösung, da die Fakultät einer natürlichen Zahl mit Ausnahme der Einheit gerade ist. Voraussetzung für ein Wertepaar $$$(n, m)$ in der Brokard-Gleichung ist die Teilbarkeit der Fakultät durch den Ausdruck:

$$

$$m ^ 2-1$$

Factorial ist per Definition ein Produkt aufeinanderfolgender natürlicher Zahlen. Anhand der Eigenschaften der natürlichen Reihen kann man den Grad der einen oder anderen Primzahl bei der kanonischen Faktorisierung der Fakultät bestimmen. Zum Beispiel $$$16!$ enthält 16 aufeinanderfolgende Faktoren. Jeder zweite Faktor wird durch 2 geteilt, jeder vierte wird durch 4 geteilt, jeder achte ist 8 und jeder 16. ist 16. Somit ist die Zerlegung $$$16!$ durch Faktoren enthält 2 zur Potenz von $$$1 + 2 + 4 + 8 = 15$ . Von hier aus, wenn es ein Paar gibt $$$(16, m)$ eine Lösung für Brokars Problem zu sein $$$m ^ 2$ muss einen Rest von 1 geben, wenn durch eine Zweierpotenz bis einschließlich 15. dividiert wird. Wir formulieren die notwendige Bedingung für $$$m$ bei der Lösung von Gleichung 1:

Lass $$$n!$ überschreitet nicht ein gewisses Maß $$$k$ Primzahl $$$p$ und es gibt eine Nummer $$$m$ bei dem das Paar $$$(n, m)$ ist eine Lösung für Gleichung 1. Dann $$$m ^ 2-1$ muss in alle Grade unterteilt werden $$$p$ vorher $$$F (k)$ wo $$$F$ - Gradberechnungsfunktion $$$p$ in Zersetzung $$$n!$ . (2)

P-Eigenschaft

Angenommen, es gibt einen Algorithmus A, der die notwendige Bedingung 2 auf eine Primzahl überprüft $$$p$ . Wir nennen einen solchen Algorithmus einen P-Test. Lass es auch eine natürliche geben $$$n$ die Bedingung erfüllen: $$$(n-1)! <m ^ 2 <n!$
Dann sagen wir, dass die Nummer $$$m$ besitzt eine P-Eigenschaft.

Betrachten Sie einen 2-Test-Prozess für beliebige $$$m$ zwischen $$$1023!$ und $$$1024!$ . Für $$$m ^ 2$ Die folgenden Aussagen sind wahr:

1. $$$m ^ 2$ ergibt einen Rest von 1, wenn durch alle Zweierpotenzen geteilt wird $$$2 ^ {1023-10 = 1013}$ einschließlich;
2. $$$m ^ 2-1$ nicht geteilt durch $$$2 ^ {1024-10 = 1014}$ .

In der Praxis liegen die meisten quadratischen Zahlen zwischen $$$1023!$ und $$$1024!$ Bestehen Sie den 2-Test in den ersten 200 Iterationen nicht. Wenn die Nummer $$$m ^ 2$ ab dem angegebenen Intervall und $$$m$ besitzt dann im binären System eine 2-Eigenschaft $$$m ^ 2$ endet in $$$100..001$ , wo die Nullen genau 1012 sind. Um Bedingung 2 zu verifizieren, können wir berechnen $$$m ^ 2$ bis zu den letzten 8 Ziffern und überprüfen Sie die letzten 8 Ziffern. Wenn es eine andere Sequenz als gibt $$$0000 0001$ dann schlug der 2-Test fehl. Sequentielle Berechnung jedes getesteten Werts mit einer Genauigkeit von 8, 16, 24 usw. Zeichen können Sie Bedingung 2 mit einem Minimum an Systemressourcen schnell auf einen großen Satz von Werten überprüfen. Die Größe von Ketten, die ein Vielfaches von 8 sind, wird durch die Bytestruktur des RAM moderner Computer gerechtfertigt: Ein ganzes Byte wird zum Speichern kleinerer Ketten verwendet. Für große Ketten, nicht Vielfache von 8, gibt es auch nicht verwendete Speicherbits.

Lassen Sie es notwendig sein, die Aussage zu überprüfen:
Unter $$$n$ aus einem Segment $$$[k_1, k_2]$ Es gibt keine Lösung für Gleichung 1 $$$m$ wo $$$n, m, k_1, k_2$ - natürlich.

Mit der Stirling-Formel definieren wir die Lücken $$$(a_1, b_1), (a_2, b_2), .., (a_l, b_l)$ wo $$$l = k_2-k_1 + 1$ . Für die i-te Lücke:

$$

$$a_i = {(s / e)} ^ s e ^ {1 / {12s + 1}} {\ sqrt {2 \ pi s}}$$

$$

$$b_i = {(s / e)} ^ s e ^ {1 / {12s}} {\ sqrt {2 \ pi s}}$$

$$

$$s = k_1 + i-1$$

Dann ist die Aussage wahr:
Wenn unter den quadratischen Zahlen von $$$(a_1, b_1), (a_2, b_2), .., (a_l, b_l)$ Keiner hat den 2-Test bestanden, dann hat Gleichung 1 keine Lösung für das Intervall $$$[k_1, k_2]$ . Das Gegenteil ist nicht wahr.

Eine Verallgemeinerung des Brokar-Problems unter den notwendigen Bedingungen

Im Allgemeinen hat eine quadratische Zahl mit einer p-Eigenschaft eine Basis im Kalkül $$$p$ Ansicht: $$$t00..001$ mit der Anzahl der Nullen $$$F (k) -1$ . Dann können wir das Problem der P-Eigenschaft verallgemeinern:
Es seien zwei Funktionen beschrieben: $$$F$ und $$$G$ Rückgabe natürlicher Werte für jedes natürliche Argument und $$$G$ kann nicht als Polynom mit ganzzahligen Koeffizienten dargestellt werden. Dann ist es notwendig, ein Kriterium zu formulieren, für das unter den Zahlen $$$m$ dazwischen liegen $$$G (t)$ und $$$G (t + 1)$ und in der Notation im Kalkül mit der Basis p die Form haben:

$$

$$k_100..00k_2 (3)$$

Sie können nur diejenigen auswählen, die eine natürliche Wurzel des n-ten Grades haben, wobei die Anzahl der Nullen in Datensatz 3 durch die Funktion angegeben wird $$$F$ abhängig $$$t$ . Dabei, $$$k_1$ kann ein Parameter, ein beliebiger Wert oder eine Konstante sein, und $$$k_2$ - immer eine Konstante. (4)

Beispielsweise können Sie das Problem der Extrahierbarkeit der Kubikwurzel aus Zahlen aufwerfen $$$n$ mit hexadezimaler Notation $$$k00..001$ wo $$$k$ Jede Hexadezimalzahl ist größer als 1 und die Anzahl der Nullen für eine bestimmte $$$n$ gleich dem größten $$$t$ für die die Ungleichung gilt:

$$

$$2 ^ t + 3t-1 <n$$

Die Grundlage für das Schreiben des Artikels war die Aussage über die direkte Beziehung zwischen der Anzahl der Nullen in Datensatz 3 in einem beliebigen Kalkül für den Wert der linken Seite von Gleichung 1 beim Ersetzen der bereits gefundenen Wurzeln und der Zahl $$$n$ . Wenn Gleichung 1 genau 3 Wurzeln hat, kann diese Tatsache durch Lösen des entsprechenden Sonderfalls von Problem 4 bewiesen werden. Das Gegenteil ist nicht der Fall.

Fazit

In Bezug auf die praktische Bedeutung abstrakter Probleme aus der Zahlentheorie als ein Faktor, der die Entwicklung des mathematischen Apparats stimuliert, ist eine interessante Gleichung in ganzen Zahlen zu erwähnen, deren Lösung im Rahmen der obigen Verallgemeinerung unmöglich ist:

$$

$$11 + ({2 ^ {n ^ 2-1} -2 ^ {3n-3}}) / (2 ^ {n-1} -1) \ equiv 0 \ pmod {2 ^ {m + 1} -1 } (5)$$

Diese Gleichung folgt logischerweise aus Versuchen, die Luke-Zahlen durch die nicht wiederkehrende Methode zu approximieren. Die Lösung von Problem 5 wird dazu beitragen, neue Eigenschaften von Mersenne-Zahlen zu entdecken und die notwendigen Bedingungen für die Beschleunigung der Arbeit verteilter Suchprogramme für große Primzahlen basierend auf dem Luc-Lemer-Test zu formulieren.

In Analogie zum schwachen Goldbach-Problem wird angenommen, dass P-Tests dazu beitragen, eine große Untergrenze für die gesamten Wurzeln von Gleichung 1 zu erhalten, außer $$$(4, 5), (5, 11)$ und $$$(7, 71)$ und die Untersuchung von Problem 3 wird zum Beweis der Unlösbarkeit von Gleichung 1 in ganzen Zahlen für ausreichend große Werte von n führen.

Quellen

Hilberts Probleme
Brokars Herausforderung