Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Generally speaking, if they ask us to prove that there are infinitely many numbers that can't be written in a certain way, how should we try to solve the problem? I've never seen a solution to such a problem yet, so I can't think of any strategy to attack the problem in the title. I think the problem leaves too many possibilities too check! If they tell me that an integer number can't be written in the form $a^2+p$ where $p$ is prime that doesn't give me any clues about how such numbers could be. I mean it doesn't put enough restrictions on the numbers that aren't of that form that I go after studying the properties of such numbers.

There is also another problem of the similar type in my book: Prove that there are infinitely many odd numbers such that they can't be written as the sum of less than 3 prime numbers.

share|improve this question
2  
The other problem is easy, if an odd number can be written as the sum of two primes, one of the two primes must be even. That restricts the possibilities considerably. –  Daniel Fischer Aug 30 '13 at 21:50

6 Answers 6

Think of numbers that are perfect squares. So is it possible to write a perfect square of $x$ as:$$x^2=a^2+p$$

share|improve this answer

Try to think of what kinds of numbers might have restrictions on how they can be written, in terms of primes and squares etc. since your problem involves primes and squares. Hint: What if $n = q^2$ where $q$ is an integer?

share|improve this answer

For your first problem, one maybe looks for numbers that are "unlikely" to be of the desired form. Take for example a perfect square $b^2$. In order for $b^2$ to be of shape $a^2+p$, we must have $b^2-a^2=p$. But because of the natural factorization $(b-a)(b+a)$, that forces $a=b-1$. So $b+a=2b-1$ must be prime.

So take any number odd $2b-1$ which is not prime. There are infinitely many of these, for example $3^2,3^3,3^4,\dots$.

Then $b^2$ cannot be expressed as $a^2+p$.

share|improve this answer

If $b^2=a^2+p$ then $b=a+1$ and $2a+1=p$. Now consider the numbers of the form $(3k+2)^2$.

share|improve this answer
    
Or, $(b-a)(b+a)=p^2$ and force $p$ not to be prime :) –  chubakueno Sep 1 '13 at 21:50

For your second problem, "less than three" means "one or two".

So, what odd numbers can't be a prime (i.e., sum of one prime) or the sum of two primes?

Is there a special prime which might help solve the second part (sum of two primes)?

share|improve this answer

The proof is given in the OEIS at A014090, where it's noted that $21679$ is the last known non-square not of the form $a^2+p$. The comments and references at A020495 are also worth a look.

share|improve this answer

Your Answer

 
discard

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.