Difficult proof involving sum of two numbers

[Jakovenko]

Homework Statement

Prove the following statement:
Every integer can be written as the sum of a prime number and an integer squared. Negative primes are allowed.

For example:
1 = (-3) + 2^2
2 = (-2) + 2^2
3 = 2 + 1^2
4 = (-5) + 3^2
5 = (-11) + 4^2
6 = 5 + 1^2
7 = 3 + 2^2
8 = 7 + 1^2
9 = 5 + 2^2
10 = (-71) + 9^2
11 = 7 + 2^2
And so forth...

The Attempt at a Solution

I naively tried to directly prove this by contradiction...but after some headshaking, there's no clear way to me to disprove the claim that this is false.

So...I puttered around and extended the examples list to the first 50 integers, but there's no clear pattern whatsoever.

Induction now seems the obvious way of proving this, but even though the statement is true for the first 50 integers, I have no idea how to show that this is true for the nth integer.

Any help would be greatly appreciated.

(Semi-random side note: for people who recognize this, its pretty similar to Goldbach's conjecture, but hopefully this one is provable)

 

[aPhilosopher]

I'm not a number theory expert by any means, but aren't there some theorems saying that the image of certain polynomials on the integers must contain a prime?

if $$n - x^{2}$$ is one for which such a theorem holds, then that should give you your solution because you would have that there exists and integer x such that $$n - x^{2} = p$$ where p is prime for every integer n.

 

[Jakovenko]

I've been thinking about your response aPhilosopher, though I'm not entirely sure what you mean by "the image" of polynomials (this isn't a pure number theory class btw, its been thrown in from a discrete mathematics class, and I've never heard your terminology before).

Are you saying that between some range X and Y there must be a prime, and if we can prove this range applies for X = x^2 and Y = (x + 1)^2 then we have the proof?

If so, I have a convoluted proof of it.

Given the formula to find the kth perfect square:
kth perfect square = 1 + 3 + 5 + 7 + 9 + ... + (2k - 1)

Let Sum_n be the sum of the first n prime numbers, and Sum_n+1 be the sum of the first (n+1) prime numbers.

Suppose there exists two consecutive squares such that k^2 and (k+1)^2 lie entirely inside the interval bounded by Sum_n and Sum_n+1.

The difference between the two squares is (2k+1).

However, the smallest difference between Sum_n+1 and Sum_n is also (2k+1), which would happen if n and n+1 were consecutive odd integers (twin primes).

Thus we have (2k+1) < Sum_n+1, because we're stating that the 2nd perfect square is less than Sum_n+1 (it must be less than Sum_n+1 to be within the range between Sum_n and Sum_n+1).

We also have (2k+1) > Sum_n+1, because 2k+1 is the smallest possible difference between Sum_n and Sum_n+1.

Clear contradiction, and thus our assumption is false, there cannot be two consecutive squares that do not have a prime number in between them. Taken the other way, there must be one or more prime numbers between each consecutive square.

So back to the very first question, yes, the range applies for X = x^2 and Y = (x + 1)^2.


But...I'm again confused where you say we can directly say there exists an integer x such that n -x^2 = p.

It almost seems to me that this is a statistics/probability question. If there are many more primes than perfect squares, then surely n - x^2 is true. But if there are very few primes compared to perfect squares, then n - x^2 might never hit a prime. We've sort of shown already that there are more primes than perfect squares, but I still don't feel comfortable saying that the statement is definitively true (where's the formal proof?)

 

[aPhilosopher]

Like I said, I'm not a number theory expert. I also have to run at the moment but I'll look at over your post more completely later. I'll also look for the theorems that I was talking about.

By the 'image' of a function $$f$$ on a set $$S$$, I meant the set $$\left\{y : \exists x \in S\ such\ that\ y = f(x)\right\}$$

There is a class of theorems that asserts that some polynomials will have at least one prime in their image on the integers.

If there aren't any such theorems that have been covered in your course though, then there is probably a better way.

 

[D H]

I don't know if this helps (I'm not a number theory expert either), but this is equivalent to showing that for all integers n the set $\{n-0,n-1,n-4,\cdots,n-k^2,\cdots\}$ contains at least one prime or negative prime.