prove or disprove that every positive integer is the sum of a perfect square and a prime number or 1 [duplicate]

I am absolutely clueless on how to prove this statement and what makes it more difficult is not knowing if it is true or false to try and find a way to prove it. Tried numbers up to 20 and it was true for all but that is not a proof that it is true for all integers. How do i go about answering this question?

marked as duplicate by Ross Millikan, JonMark Perry, Claude Leibovici, Daniel W. Farlow, Daniel Robert-NicoudMar 19 '16 at 14:09

• hmmm. how did you come by this question? – Will Jagy Dec 19 '13 at 19:31
• I am going back through a course i took a few years back and solving every question in the book but i am stuck on this 1 – george Dec 19 '13 at 19:32
• What about 25?? – Mike Dec 19 '13 at 19:35
• does bunyakovsky imply this? – Jorge Fernández Hidalgo Dec 19 '13 at 19:57
• What was being discussed in the book in the chapter that includes this problem? What was the book? – Will Jagy Dec 19 '13 at 20:33

Primes are positive.

So, 25 is not so expressible. The sequence of non-expressible integers begins 25,34,58,64,85,91,121,130,169,196,214,289,324,... and is A014090 at the OEIS.

There, Dean Hickerson gives a proof that this sequence is infinite. Note that the allowance of the number 1 as an honorary prime does not cause difficulty, since a square cannot differ by 1 from a square.

Added: Dean's proof goes like this. Let $n$ be a positive integer such that $2n-1$ is composite. Then if we can write $n^2$ as the sum of a square and a prime, we'll have $$n^2 = m^2 + p$$ for some integer $m$ and some prime $p>0$. Then, $$p = n^2-m^2 = (n-m)(n+m).$$ Since $p$ is prime, we must have $$n-m=1$$ and so $p=n+m=2n-1$, which contradicts the primality of $p$. So $n^2$ is not so representable.

Now, if we allow negative primes, we simply modify this and consider positive $n$ such that $2n-1$ and $2n+1$ are composite. Then if $n^2=m^2+p$ for some integer $m$ and some prime $p$, possibly negative, we have $$p =n^2-m^2 = (n-m)(n+m)$$ and so $n-m=\pm 1$ and $n+m=2n+1$ or $n+m=2n-1$. Since both values are composite, this contradicts $p$'s primality. So $n^2$ is not so representable.

Now, there are infinitely many such $n$. Consider, for example, $n$ of the form $$n = 13+15r$$ for $r$ a positive integer. Then $$2n-1 = 25+30r = 5(5+6r)$$ and $$2n+1 = 27+30r = 3(9+10r)$$ are both composite, and so there are infinitely many integers not representable as the sum of a square and a prime (positive or negative).

• not according to the text i am using hungerford, he is defining a prime number to be an integer other than 1 or -1 whose only devisors are p, -p, 1, -1 – george Dec 20 '13 at 1:48
• How odd. This breaks unique factorization, among other things. – Matthew Conroy Dec 20 '13 at 2:20
• I did find this problem in a set of lecture notes by Ulrich Meierfrankenfeld, at Michigan State. But I do not see it in the original book by Hungerford. So it is possible that Prof. Meierfrankenfeld put in this question after saying that primes were always positive for his course. – Will Jagy Dec 20 '13 at 3:56
• i dont think that this breaks unique factorisation because he does say that every number can be written uniquely as a product of positive primes – george Dec 20 '13 at 4:03
• it is on page 18 question 24 in hungerford so supposedly a beginning problem – george Dec 20 '13 at 4:07