# Does there exist such a positive integer?

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.

• What's the source of your problem? – Xam Dec 28 '16 at 19:08
• If you consider $3(M^{2^k})-1$, then yes. Take $M=1$. Otherwise, with $2$, no. – Dietrich Burde Dec 28 '16 at 19:10
• 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. – David K Dec 28 '16 at 19:11
• @user398623 if you get an answer to this question anytime soon you can be sure that it's going to be negative. – Jorge Fernández Hidalgo Dec 28 '16 at 19:19
• There exists infinitely many integers which are not sum of a square and a prime. – user398623 Dec 28 '16 at 20:56

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.

https://oeis.org/A020495

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.

• 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. – user398623 Dec 29 '16 at 18:16