Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

We wish to find the set of natural numbers that cannot be expressed as a difference between a square and a prime.


$1 = 2^2 - 3$

$2 = 3^2 - 7$

$3 = 4^2 - 13$

and so on.

The smallest such number is $16$. The proof that $16$ cannot be expressed as a difference of a square and a prime:

Let $r^2 - p = 16$ for natural number $r$ and prime $p$

$\implies (r-4)(r+4) = p$

$\implies r-4 = 1$ since the two factors of $p$ are $p$ and $1$

$\implies r = 5$ but then $r + 4 = 9$ which is not a prime.

In general, this is true for all $n^2$ where $2n + 1$ is composite since the same reasoning applies. Therefore $49, 100, 144, 169..$ can be seen to belong to this set.

The question is whether all the numbers which cannot be expressed like this are of this form i.e. $n^2$ where $2n + 1$ is composite. A brute force search shows that this holds true for numbers less than 10000.

share|cite|improve this question
A similar question is asked at… – A.K. May 23 '14 at 13:10
I dont konw what's the question,if is this: "The question is whether all the numbers which cannot be expressed like this are of this form i.e. n2 where 2n+1 is composite.", my answer is : yes,it is. If $2n+1$ is composite,$\ n$ must of the form $2ij + i + j,\ i, j \in\mathbb{Z},\ 1 \le i \le j\ $, see [Sieve of Sundaram]( Let $n = 2ij + i + j,\ $this question is equivalent to prove :$(n+x)^2 - n^2 $ is composite,where $x \in\mathbb{Z^+}$, this is a elementary question, I dont understand this is related to some conjecture. – Mike May 24 '14 at 6:01
@Mike: How do you show that a number that cannot be expressed like this must be a square in the first place? – Emil Jeřábek May 24 '14 at 10:44

2 Answers 2

up vote 20 down vote accepted

We have a representation $m=x^2-p$ where $m$ and $x$ are positive integers and $p$ is a prime if and only if there is a prime of the form $x^2-m$. Little is known about primes of the form $x^2-m$; it has not been proved for any fixed value of $m$ that there are infinitely many such primes. However, Bunyakovsky's conjecture (or in fact a special case of it) would imply that $x^2-m$ is prime for infinitely many $x$ unless $m$ is a square. So, if we assume this conjecture, every non-square is the difference of a square and a prime. And if $m=n^2$ is a square, then clearly the representation is possible if and only if $2n+1$ is a prime.

It is of course a weaker claim that the sequence $x^2-m$ contains one prime than infinitely many, but proving this weaker statement for all non-squares $m$ might be almost as hard as proving the stronger statement. For example, proving Dirichlet's theorem about primes in arithmetic progressions is esentially as hard as showing that the sequence $an+b$ contains at least one prime for all coprime $a$ and $b$.

share|cite|improve this answer
I assume this means that the problem is open.. – A.K. May 23 '14 at 14:53
Very likely. Also the OEIS article says it's a conjecture. – Joni Teräväinen May 23 '14 at 17:43

See also OEIS sequence A075555.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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