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, 2021 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, 2021 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, 2021 at 7:48
  • 2
    $\begingroup$ @Neinstein, one possible application is provided here: bitsdeep.com/posts/attacking-rsa-for-fun-and-ctf-points-part-2 $\endgroup$ Aug 5, 2021 at 10:56

2 Answers 2

22
$\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$
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .