2
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Daniel Fischer Aug 30 '13 at 21:50
8
$\begingroup$

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

|cite|improve this answer
$\endgroup$
4
$\begingroup$

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?

|cite|improve this answer
$\endgroup$
3
$\begingroup$

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$.

|cite|improve this answer
$\endgroup$
3
$\begingroup$

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

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

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.

|cite|improve this answer
$\endgroup$
2
$\begingroup$

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)?

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.