Gibt es unendlich viele Fermat-Primzahlpaare?

Question

Gibt es unendlich viele Fermat-Primzahlpaare?

Mathematik
Zahlentheorie
Primzahlen
Primfaktorisierung
Elementarzahlentheorie

Kette Markov

Vermuten $p$ Und $q$ sind Primzahlen. Nennen wir das Paar $(p, q)$ ein Fermat-Paar iff $| p - q | < 2\sqrt{2} (pq)^{\frac{1}{4}}$ .

Solche Primzahlpaare besitzen eine ziemlich interessante Eigenschaft: Sie können sauber ausgedrückt werden, indem nur ihr Produkt verwendet wird (obwohl die Primzahlzerlegung im Allgemeinen ein rechentechnisch schwieriges Problem ist). Wenn ich mich richtig erinnere, wurde diese Tatsache zuerst von Pierre de Fermat entdeckt (daher der Name der Paare).

Konkret, wenn $N = pq$ Und $p > q$ , Dann

P = ⌊ \sqrt{N} ⌋ + 1 + \sqrt{(⌊ \sqrt{N} ⌋ + 1)^{2} - N}

$p = \lfloor \sqrt{N} \rfloor + 1 + \sqrt{(\lfloor \sqrt{N} \rfloor + 1)^2 - N}$

Q = ⌊ \sqrt{N} ⌋ + 1 - \sqrt{(⌊ \sqrt{N} ⌋ + 1)^{2} - N}

$q = \lfloor \sqrt{N} \rfloor + 1 - \sqrt{(\lfloor \sqrt{N} \rfloor + 1)^2 - N}$

Nachweisen:

Vermuten $a = \frac{p + q}{2}$ Und $b = \frac{p - q}{2}$ . Dann $N = a^2 - b^2$ . Jetzt ab $b < \sqrt{2} N^{\frac{1}{4}} < \sqrt{2a}$ das können wir ableiten $(a-1)^2 \leq N < a^2$ , was uns unsere Formeln liefert.

Meine Frage ist:

Gibt es unendlich viele Fermat-Paare?

Wenn die Antwort bekannt ist, sollte sie positiv sein. Warum? Weil jedes Paar von Primzahlzwillingen ein Fermat-Paar ist. Daher hätte die negative Antwort auf diese Frage eine negative Antwort auf die Twin-Prime-Vermutung gegeben (und dieses Problem ist derzeit offen).

Wenn es jedoch bekannt ist, würde ich gerne einen Beweis dafür sehen, dass es unendlich viele Fermat-Paare gibt.

Roddy McPhee

Sofern nicht nur endlich viele keine Primzahlzwillinge sind, müssten Sie die Primzahlzwillinge beweisen.

Eric Wong

Twin-Prime-Vermutung ist für dieses Problem ein Mega-Overkill. Sie müssen nur zeigen, dass die

n

$n$ te Primzahl ist

o (n^{2})

$o(n^2)$ . Es folgt also leicht aus dem Primzahlsatz und kann möglicherweise aus etwas Klassischerem wie dem von Euler extrahiert werden

\sum 1 / p = \infty

$\sum 1/p = \infty$ .

Neinstein

Interessiert: hat diese Eigenschaft tatsächlich eine sinnvolle Anwendung? Für mich scheint es keine Hilfe bei der Primfaktorzerlegung zu bieten, da Sie die Primfaktoren a priori kennen müssen , um festzustellen, ob N ein Fermat-Produkt ist.

Kette Markov

@Neinstein, eine mögliche Anwendung wird hier bereitgestellt: bitsdeep.com/posts/attacking-rsa-for-fun-and-ctf-points-part-2

Antworten (2)

Gibt es unendlich viele Fermat-Primzahlpaare?

Sofern nicht nur endlich viele keine Primzahlzwillinge sind, müssten Sie die Primzahlzwillinge beweisen.
Twin-Prime-Vermutung ist für dieses Problem ein Mega-Overkill. Sie müssen nur zeigen, dass die $n$ te Primzahl ist $o(n^2)$ . Es folgt also leicht aus dem Primzahlsatz und kann möglicherweise aus etwas Klassischerem wie dem von Euler extrahiert werden $\sum 1/p = \infty$ .
Interessiert: hat diese Eigenschaft tatsächlich eine sinnvolle Anwendung? Für mich scheint es keine Hilfe bei der Primfaktorzerlegung zu bieten, da Sie die Primfaktoren a priori kennen müssen , um festzustellen, ob N ein Fermat-Produkt ist.
@Neinstein, eine mögliche Anwendung wird hier bereitgestellt: bitsdeep.com/posts/attacking-rsa-for-fun-and-ctf-points-part-2

Eierlog · Answer 1

Es ist bewiesen, dass es unendlich viele Primzahlen gibt, die sich höchstens um 246 unterscheiden. Also mit $p > q$ , Sie haben unendlich viele Fälle davon $p - q \leq 246$ .

Aber lösen $2\sqrt{2}(pq)^{\frac{1}{4}} > 246$ Erträge $pq > \left(\frac{123}{\sqrt{2}}\right)^4$ . Seit $p = q + k$ mit $k$ maximal $246$ , kann dies leicht gelöst werden, um zu zeigen, dass es eine endliche untere Schranke gibt $p$ , für die alle $p$ größer als diese Grenze löst die Ungleichung und erfüllt damit die Bedingung eines Fermat-Paares.

Links finden Sie hier: https://asone.ai/polymath/index.php?title=Bounded_gaps_between_primes

Mischa Lawrow · Answer 2

Der Primzahlsatz besagt, dass es sie gibt $(1 + o(1)) \frac{n}{\ln n}$ Primzahlen kleiner oder gleich $n$ . Insbesondere für groß genug $n$ , gibt es zumindest $\frac{n^2}{2 \ln (n^2)} - \frac{2n}{\ln n}$ Primzahlen dazwischen $n$ Und $n^2$ .

In diesem Bereich zu haben $|p-q| < 2 \sqrt{2} (pq)^{1/4}$ , es ist mehr als genug, das zu fragen $|p-q| < 2 \sqrt{2n}$ ; nahe der Spitze dieses Bereichs, das ist übertrieben.

Wenn jedoch keine Primzahlen dazwischen lägen $n$ Und $n^2$ das sind weniger als $2\sqrt{2n}$ auseinander, dann gäbe es höchstens $\frac{n^2 - n}{2 \sqrt {2n}}$ Primzahlen in diesem Bereich, der kleiner als ist $\frac{n^2}{2 \ln (n^2)} - \frac{2n}{\ln n}$ Wenn $n$ ist groß.

Daher für jeden ausreichend groß $n$ , gibt es ein Fermat-Primzahlpaar im Bereich von $n$ Zu $n^2$ , was uns unendlich viele solcher Paare gibt.

Gibt es unendlich viele Fermat-Primzahlpaare?

Kette Markov

Roddy McPhee

Eric Wong

Neinstein

Kette Markov

Antworten (2)

Eierlog

Mischa Lawrow

Die Primzahlzerlegung der Summe zweier Quadrate

Meine Beobachtung zu Prime Gap

Welche Bedeutung hat die Collatz-Vermutung?

Beweisen Sie, dass es keine 5-stelligen EXTREME PRIMES gibt.

Methode, um herauszufinden, ob ein Polynom irrationale Wurzeln hat?

Über die Koprimalität armbandartiger Zahlen

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

Naive kategorische Frage zu Primzahlen, Primzahlen und Irreduziblen

Wie viele ganze Zahlen gibt es, die nicht durch eine Primzahl größer als 20 und nicht durch das Quadrat einer Primzahl teilbar sind?

Sei pkpkp_k die kkkte Primzahl, kann für p≥5p≥5p \ge 5 gezeigt werden, dass es zwischen p2kpk2p_k^2 und p2k+1pk+12p_{k+1}^2 nicht immer einen Primzahlzwilling gibt?