Das Folgende ist eine notwendige Bedingung dafür, dass eine Zahl aufgrund ihrer Ziffernerweiterung eine Primzahl ist. Wurde es irgendwo verwiesen?

In Bezug auf die Ziffern einer Zahl kennen wir einige notwendige Bedingungen, damit die Zahl eine Primzahl ist, abgesehen davon, dass die letzte Ziffer ungerade sein muss (außer Primzahl 2). Zum Beispiel kann in der Dezimaldarstellung die letzte Ziffer nicht 5 sein, und die Summe der Ziffern der Zahl kann nicht durch 3 teilbar sein. Aber wurde das folgende Ergebnis irgendwo erwähnt?

  1. Nehmen wir die Ziffernerweiterung einer natürlichen Zahl N in Positionsnotation mit seinen M Ziffern, die in zwei fortlaufende verkettete Zeichenfolgen unterteilt sind A Und B so dass:

    N = A 2 k + B  mit 

    B = B 0 R 0 + ⋯ + B k − 1 R k − 1

    A = A 0 R 0 + ⋯ + A M − k − 1 R M − k − 1

    R = Radius (der Basis, auf der die Zahl dargestellt wird)

    M = Anzahl der Ziffern von N ( M > k )

  2. Dann könnten wir die folgende notwendige Bedingung für die Ziffernerweiterung der Zahl angeben, damit sie eine Primzahl ist:

    Für alle B > 1 , es kann keine geben k so dass A  Mod  B = 0

    Beweis: Gäbe es, könnten wir schreiben N als Produkt:

    N = ( A B R k + 1 ) B

Beispiel:

Nehmen Sie die Zahl 637 in Basis 10. Sie müssen alle möglichen Kombinationen von zwei Zeichenfolgen mit a>=b überprüfen.

In diesem Fall ist es einfach, es funktioniert wie folgt: a='63' und b='7'.

Da a/b = 63/7=9 ist, können Sie 637=((63/7)*10 + 1)*7 schreiben

Also kann 637 keine Primzahl sein.

Ich habe diese Eigenschaft erkannt, als ich in einem anderen „Zahlensystem“ als unserem eigenen gearbeitet habe, wo die Arithmetik anders ist. Dann kam Gustavo Granja freundlicherweise zu dieser Formulierung, die in unserem „üblichen“ Zahlensystem äquivalent ist.

Es scheint zu einfach, nicht bekannt zu sein. In MathOverflow erhielt ich den folgenden hilfreichen Kommentar von Gerhard Paseman: „Dies ist eine spezifische Version von etwas Allgemeinerem: Wenn N = A C + B mit A , B , C positiv und B > 1 , Dann B | A impliziert N ist keine Primzahl".

Trotz dieses allgemeinen Falls finde ich es jedoch interessant (und schließlich hilfreich für Faktorisierungszwecke), dass wir dies manchmal direkt aus den Ziffern einer Zahl erkennen können, ohne Teilbarkeitstests, die andere Informationen als die unmittelbar vor uns haben Augen.

Daher frage ich mich, ob das schon irgendwo erwähnt wurde.

Wenn ich solche Dinge aufschreibe, finde ich es nützlich, einige Beispiele dafür zu geben, wie man die Aufteilung in verkettete Zeichenfolgen auf der Basis zehn und dann auch auf einer anderen Basis durchführt.
Vielen Dank für den hilfreichen Vorschlag Timbuc. Im Moment habe ich nur ein Beispiel in Basis 10 hinzugefügt, aber es ist die gleiche Logik in jeder Basis. Wie auch immer, wenn ich Zeit habe, könnte ich andere Beispiele hinzufügen.

Antworten (1)

Ihre Beobachtung ist ein Spezialfall inhaltsbasierter Faktoren von Polynomen.

Nehme an, dass F ( X ) ist ein nicht konstantes Polynom, dessen Koeffizienten alle nicht negative ganze Zahlen sind.     Wenn F hat nichttrivialen Inhalt, dh wenn der gcd D aller Koeffizienten von F Ist > 1 , dann folgt das D ∣ F ( N ) richtig für alle N > 1 , So F ( N ) ist zusammengesetzt für alle N > 1 .

Dies gilt für OP, da die Radix-Notation eine Polynomfunktion der Basis (des obigen Typs) ist.

Anmerkung   Es gibt viele interessante Beziehungen zwischen den Faktorisierungseigenschaften von Polynomen und ihren Werten. Zum Beispiel im 1918 Stackel hat folgendes veröffentlicht

Satz Wenn F ( X ) dann ein zusammengesetztes ganzzahliges Koeffizientenpolynom ist F ( N ) ist zusammengesetzt für alle | N | > B , für einige gebunden B . In der Tat F ( N ) hat höchstens 2 D Prime-Werte, wo D = D e G ( F ) .

Den einfachen Beweis findet man online in Mott & Rose [3] , p. 8.

Im Gegenteil, F ( X ) ist prim (irreduzibel), wenn sie für groß genug einen Primwert annimmt | X | . Als Beispiel hat Polya-Szego den Irreduzibilitätstest von A. Cohn populär gemacht, der dies besagt F ( X ) ∈ Z [ X ] ist prim wenn F ( B ) ergibt eine Primzahl in Basis B Vertretung (so 0 ≤ F ich < B ) .

Zum Beispiel F ( X ) = X 4 + 6 X 2 + 1 ( Mod P ) Faktoren für alle Primzahlen P , noch F ( X ) ist prim da F ( 8 ) = 10601 oktal = 4481 ist prim. Der Cohn-Test schlägt fehl, wenn in Radix B , negative Ziffern sind erlaubt, z F ( X ) = X 3 − 9 X 2 + X − 9 = ( X − 9 ) ( X 2 + 1 ) Aber F ( 10 ) = 101 ist prim.

Umgekehrt vermutete Bouniakowski ( 1857 ) diese Primzahl F ( X ) nehmen unendlich viele Primwerte an (mit Ausnahme von Fällen, in denen alle Werte von F feste gemeinsame Teiler haben, z 2 | X ( X + 1 ) + 2 ) . Abgesehen von linearen Polynomen (Satz von Dirichlet) wurde diese Vermutung jedoch nie für Polynome des Grades bewiesen > 1.

Beachten Sie, dass sich ein Ergebnis, das die Existenz eines Primzahlwerts ergibt, auf die Existenz unendlich vieler Primzahlwerte erstreckt, und zwar für jede Klasse von Polynomen, die unter Verschiebungen abgeschlossen sind, d. h. Wenn F ( N 1 ) ist dann prim G ( X ) = F ( X + N 1 + 1 ) ist für manche das Wichtigste X = N 2 ∈ N , usw.

Für eine weitere detaillierte Diskussion von Bouniakowskis Vermutung und verwandten Ergebnissen, einschließlich heuristischer und probabilistischer Argumente, siehe Kapitel 6 von Ribenboims The New Book of Prime Number Records .

[1] Bill Dubuque, sci.math 2002-11-12, Über Primzahl produzierende Polynome.

[2] Murty, Widder. Primzahlen und irreduzible Polynome.
Amer. Mathematik. Monatlich, Bd. 109 (2002), Nr. 5, 452-458.

[3] Mott, Joe L.; Rosa, Kermit. Primzahlerzeugende kubische Polynome.
Ideale theoretische Methoden in der kommutativen Algebra, 281-317.
Vorlesungsnotizen in Pure und Appl. Math., 220, Dekker, New York, 2001.

Auch ohne die bereitgestellten interessanten Referenzen untersucht oder die Möglichkeit anderer Antworten in Betracht gezogen zu haben, habe ich diese Antwort von den ersten Absätzen an als den wertvollsten Link akzeptiert, um das Problem im Rahmen der Polynome zu betrachten, was für meine zukünftige Promotion sehr hilfreich sein könnte hinter dieser Frage arbeiten. Abgesehen davon, dass es funktioniert, hat mir die Antwort die notwendige allgemeine Einstellung gegeben, ohne die Spezifität der Ziffernerweiterung zu verlassen. Also vielen Dank.
Das Folgende ist eine notwendige Bedingung dafür, dass eine Zahl aufgrund ihrer Ziffernerweiterung eine Primzahl ist. Wurde es irgendwo verwiesen?
AntwortenHierDatenschutz-Bestimmungen1y, 1v