Does there exist such a positive integer $M$ such that, $2\left(M^{2^k}\right)-1$ is prime for all $k= 0, 1, 2, \dotsc$?

I was trying to solve the problem:

Show that there are infinitely many integers which are not sum of a prime and a square.

I ended up showing that there are infinitely many numbers of the form $3k + 1$ which are not sum of a square and a prime. But then I was trying to find a different solution. I assumed that there are finitely many such numbers, and that $M$ is the biggest number which can't be written as a sum of a prime and a square. Then I tried to derive a contradiction by showing that there exists and integer $N$ greater than $M$ such that $N$ is a sum of a square and a prime.enter image description here

  • $\begingroup$ What's the source of your problem? $\endgroup$
    – Xam
    Dec 28, 2016 at 19:08
  • 1
    $\begingroup$ If you consider $3(M^{2^k})-1$, then yes. Take $M=1$. Otherwise, with $2$, no. $\endgroup$ Dec 28, 2016 at 19:10
  • 3
    $\begingroup$ If such an integer $M$ existed and we knew its value, it would put an end to the whole business of finding "the largest known prime". That doesn't prove anything, of course. $\endgroup$
    – David K
    Dec 28, 2016 at 19:11
  • 1
    $\begingroup$ @user398623 if you get an answer to this question anytime soon you can be sure that it's going to be negative. $\endgroup$
    – Asinomás
    Dec 28, 2016 at 19:19
  • 1
    $\begingroup$ There exists infinitely many integers which are not sum of a square and a prime. $\endgroup$
    – user398623
    Dec 28, 2016 at 20:56

1 Answer 1


Evidently this is part of a contest problem. The question was to show that there are infinitely many natural numbers that cannot be written as a square plus a prime. If you do a simple computer run, you find that such numbers are usually squares themselves. Furthermore, the set of such numbers that are not squares seems to be finite. This is, indeed Hardy and Littlewood's Conjecture H.



On page 36, problem 3.3.1 in The Hardy-Littlewood Method, by R. C. Vaughan, one is asked to prove that all sufficiently large natural numbers can be written as $p_1+p_2+x^k,$ for fixed exponent $k \geq 2.$

On the other hand, the set of squares that cannot be written as a smaller square plus a prime is, evidently, infinite.

Take any natural number $$ n \equiv 2 \pmod 3 $$. Take any smaller number $$ 1 \leq m < n $$ If $$ n^2 - m^2 = (n + m)(n-m) $$ is prime, the only possibility is $n-m=1$ or $m = n-1.$ Alright, assume $$ n^2 - (n-1)^2 $$ is prime. Well $$ n^2 - (n-1)^2 = 2n - 1. $$ However, $$ 2n-1 \equiv 2 \cdot 2 -1 \equiv 0 \pmod 3 $$ is divisible by $3$ and not prime.

So, $n^2$ is not the sum of a prime and a smaller square.

  • 1
    $\begingroup$ Thanks a lot for this. I am really amazed by the hardy and littlewood's conjecture. But here I am not asking for the solution of the problem you mentioned. I have solved it. I am asking if there exists any integer with the property I stated. $\endgroup$
    – user398623
    Dec 29, 2016 at 18:16

You must log in to answer this question.

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