16
$\begingroup$

Suppose $p$ and $q$ are prime numbers. Let’s call the pair $(p, q)$ a Fermat pair iff $| p - q | < 2\sqrt{2} (pq)^{\frac{1}{4}}$.

Such prime pairs possess a rather interesting property: they can neatly be expressed using only their product (even though prime decomposition is generally a computationally hard problem). If I recall correctly, this fact was first discovered by Pierre de Fermat (hence the name of the pairs).

To be concrete, if $N = pq$ and $p > q$, then

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

Proof:

Suppose $a = \frac{p + q}{2}$ and $b = \frac{p - q}{2}$. Then $N = a^2 - b^2$. Now, from $b < \sqrt{2} N^{\frac{1}{4}} < \sqrt{2a}$ we can derive that $(a-1)^2 \leq N < a^2$, which yields us our formulas.

My question is:

Are there infinitely many Fermat pairs?

If the answer is known, it should be positive. Why? Because any pair of twin primes is a Fermat pair. Therefore the negative answer to this question would have given negative answer to the Twin Prime Conjecture (and that problem is currently open).

However, if it is known, I would like to see a proof that there are infinitely many Fermat pairs.

$\endgroup$
4
  • $\begingroup$ Unless it's only finitely many that aren't twin primes, you'd have to prove the twin prime connection. $\endgroup$ Aug 4 at 20:43
  • 2
    $\begingroup$ Twin prime conjecture is mega-overkill for this problem. You only need to show that the $n$th prime is $o(n^2)$. So it easily follows from Prime Number Theorem, and potentially can be extracted from something more classical like Euler's $\sum 1/p = \infty$. $\endgroup$
    – Erick Wong
    Aug 4 at 21:32
  • $\begingroup$ Interested: does this property have an actual meaningful application? To me, it seems it offers no help in prime factorization, since you have to know the prime factors a priori to determine if N is a Fermat product. $\endgroup$
    – Neinstein
    Aug 5 at 7:48
  • 1
    $\begingroup$ @Neinstein, one possible application is provided here: bitsdeep.com/posts/attacking-rsa-for-fun-and-ctf-points-part-2 $\endgroup$ Aug 5 at 10:56
19
$\begingroup$

The prime number theorem says that there are $(1 + o(1)) \frac{n}{\ln n}$ primes less than or equal to $n$. In particular, for large enough $n$, there are at least $\frac{n^2}{2 \ln (n^2)} - \frac{2n}{\ln n}$ primes between $n$ and $n^2$.

In this range, to have $|p-q| < 2 \sqrt{2} (pq)^{1/4}$, it's more than enough to ask that $|p-q| < 2 \sqrt{2n}$; near the top of that range, that's overkill.

However, if there were no primes between $n$ and $n^2$ that are less than $2\sqrt{2n}$ apart, then there would be at most $\frac{n^2 - n}{2 \sqrt {2n}}$ primes in that range, which is less than $\frac{n^2}{2 \ln (n^2)} - \frac{2n}{\ln n}$ when $n$ is large.

Therefore, for every sufficiently large $n$, there is a Fermat prime pair in the range from $n$ to $n^2$, which gives us infinitely many such pairs.

$\endgroup$
20
$\begingroup$

It has been proven that there an infinitely many primes that differ by at most 246. Therefore, with $p > q$, you have infinitely many cases such that $p - q \leq 246$.

But, solving $2\sqrt{2}(pq)^{\frac{1}{4}} > 246$ yields $pq > \left(\frac{123}{\sqrt{2}}\right)^4$. Since $p = q + k$ with $k$ at most $246$, this can readily be solved to show that there is a finite lower bound on $p$, for which all $p$ bigger than this bound solves the inequality thus satisfying the condition of a Fermat pair.

Links can be found here: https://asone.ai/polymath/index.php?title=Bounded_gaps_between_primes

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.