Can anyone please verify/review this counterexample?

[Math100]

Homework Statement

Give an example to show that the following conjecture is not true: Every positive integer can be written in the form p+a^2, where p is either a prime or 1, and a$\geq$0.

Relevant Equations

None.

Disproof: Here is a counterexample:
Suppose p+a^2=25, where 25 is a positive integer.
Then we have 25=0+25
=9+16
=16+9
=21+4.
Note that none of 0, 4, 9, and 16 is prime or 1.
Therefore, not every positive integer can be written in the form p+a^2,
where p is either a prime or 1, and a$\geq$0.

Above is my proof/answer for this problem. Can anyone please review/verify if it's correct?

 

[fresh_42]

Homework Statement:: Give an example to show that the following conjecture is not true: Every positive integer can be written in the form p+a^2, where p is either a prime or 1, and a$\geq$0.
Relevant Equations:: None.

Disproof: Here is a counterexample:
Suppose p+a^2=25, where 25 is a positive integer.
Then we have 25=0+25
=9+16
=16+9
=21+4.
Note that none of 0, 4, 9, and 16 is prime or 1.
Therefore, not every positive integer can be written in the form p+a^2,
where p is either a prime or 1, and a$\geq$0.

Above is my proof/answer for this problem. Can anyone please review/verify if it's correct?

25=1+24 is missing, and why did you require $a\geq 0$?

 

[Math100]

Okay, so it should be the following:
Then we have 25=0+25
=1+24
=21+4
=9+16
=16+9.
Regarding a$\geq$0, I didn't require it, the problem statement had the condition so I included at the end of my proof.

 

[fresh_42]

Here is another one: $x^2+x+41$ is always prime for $x\in \mathbb{N},$ true or not?

 

[Math100]

Here is another one: $x^2+x+41$ is always prime for $x\in \mathbb{N},$ true or not?

Yes, it's true.

 

[fresh_42]

Yes, it's true.

Nope. It is not, but it takes some numbers until it is false. What about $x=41$?

 

[Math100]

And for the 25=1+24, I think I would write it as 25=24+1 because in this case, p=24 and a^2=1. Thus, 24 is neither a prime nor 1.

 

[fresh_42]

And for the 25=1+24, I think I would write it as 25=24+1 because in this case, p=24 and a^2=1. Thus, 24 is neither a prime nor 1.

Yes, and $p=1$ is an option offered by the problem statement, but $24$ isn't a square!

 

[Math100]

Nope. It is not, but it takes some numbers until it is false. What about $x=41$?

For x=41, x^2+x+41 is not prime, so the answer is false.

 

[Math100]

Yes, and $p=1$ is an option offered by the problem statement, but $24$ isn't a square!

So you're implying that in order to provide a counterexample of x=25, we just need to show that 25=1+24 and explain that 24 isn't a perfect square, that will suffice the whole/complete disproof for this problem?

 

[fresh_42]

So you're implying that in order to provide a counterexample of x=25, we just need to show that 25=1+24 and explain that 24 isn't a perfect square, that will suffice the whole/complete disproof for this problem?

I'm saying that you have to check all expressions $p+a^2$ whether they equal $25$ or not.
$25=24+1$ where $p=24$ and $a^2=1$ is one possibility ($24$ is not prime), but the problem said, that $p=1$ is allowed, too, so $p=1$ and $a^2=24$ is another possibility ($24$ isn't a perfect square). In any case, $24+1$ isn't an allowed solution.

 

[fresh_42]

By the way, now that we talk about primes. A prime is a number that, if it divides a product, then it already divides one of the factors. This is the real definition.
$$
p\,|\,a\cdot b \Longrightarrow p\,|\,a \text{ or } p\,|\,b
$$
You can see, that this wouldn't make sense for $p=1$ because $1$ divides everything. This is why $p=1$ isn't considered a prime.

 

[Math100]

I'm saying that you have to check all expressions $p+a^2$ whether they equal $25$ or not.
$25=24+1$ where $p=24$ and $a^2=1$ is one possibility ($24$ is not prime), but the problem said, that $p=1$ is allowed, too, so $p=1$ and $a^2=24$ is another possibility ($24$ isn't a perfect square). In any case, $24+1$ isn't an allowed solution.

So do I still need to write/include all other possibilities like 25=0+25
=21+4
=9+16
=16+9.
I don't think showing these are necessary because 25=1+24 is the perfect counterexample for this problem.

 

[WWGD]

I'd say it's impossible for squares: If $p+ a^2= b^2$, then $p =b^2 -a ^2 =(b-a)(b+a)$, a contradiction, unless $b-a=1$..

 

[Steve4Physics]

Homework Statement:: Give an example to show that the following conjecture is not true: Every positive integer can be written in the form p+a^2, where p is either a prime or 1, and a$\geq$0.
Relevant Equations:: None.

Disproof: Here is a counterexample:
Suppose p+a^2=25, where 25 is a positive integer.
Then we have 25=0+25
=9+16
=16+9
=21+4.
Note that none of 0, 4, 9, and 16 is prime or 1.
Therefore, not every positive integer can be written in the form p+a^2,
where p is either a prime or 1, and a$\geq$0.

Above is my proof/answer for this problem. Can anyone please review/verify if it's correct?

Your working could be clearer. For example, a clear, consistently formatted list (of ways to express 25 in the form $p + a²$) could be written:
25 + 0²
24 + 1²
21 + 2²
etc.

Also, the question does not explicitly say $a$ is an integer. You may be expected to also cover non-integer values of $a$.

 

[fresh_42]

So do I still need to write/include all other possibilities like 25=0+25
=21+4
=9+16
=16+9.
I don't think showing these are necessary because 25=1+24 is the perfect counterexample for this problem.

No, you have to check all possibilities. The fact that $25=0+25$ isn't a solution doesn't mean that $25=1+24$ couldn't be one. All possibilities must be excluded to get a counterexample for $25=p+a^2.$

 

[Math100]

No, you have to check all possibilities. The fact that $25=0+25$ isn't a solution doesn't mean that $25=1+24$ couldn't be one. All possibilities must be excluded to get a counterexample for $25=p+a^2.$

Okay, so I revised the whole disproof:
Suppose p+a^2=25, where 25 is a positive integer.
Then we have 25=0+25=0+5^2
=21+4=21+2^2
=9+16=9+4^2
=16+9=16+3^2
=1+24=1+(sqrt(24))^2
=24+1=24+1^2.
Note that 0, 9, 16 and 21 are not prime numbers or 1.
Also note that 24 is not a perfect square, prime number or 1.
Therefore, not every positive integer can be written in the form p+a^2,
where p is either a prime or 1, and a$\geq$0.

 

[fresh_42]

I'd say it's impossible for squares: If $p+ a^2= b^2$, then $p =b^2 -a ^2 =(b-a)(b+a)$, a contradiction, unless $b-a=1$..

Edit: $b-a=1$ makes $p=b+a=1+2a$ and $25=p+a^2=a^2+2a+1=(a+1)^2.$ Thus $a=4$ and $25=p+4^2$ means $p=9$ which is not prime.

To complete the argument: The above shows that $p+a^2$ isn't a perfect square, if $p$ is prime. That leaves us with the case $p=1.$ This results in $1=(b-a)(b+a)$ which can only be true for $b=1$ and $a=0.$ But $p+a^2=1+0^2=1\neq 25,$ so again no solution.

 

[Math100]

Then we have 25=25+0^2
=24+1^2
=21+2^2
=16+3^2
=9+4^2
=0+5^2.
Note that none of 0, 9, 16, 21, 24 and 25 are prime numbers or 1.

 

[PeroK]

Then we have 25=25+0^2
=24+1^2
=21+2^2
=16+3^2
=9+4^2
=0+5^2.
Note that none of 0, 9, 16, 21, 24 and 25 are prime numbers or 1.

That's okay. Note that if we consider any perfect square $n^2$ and look for $n^2 = p + a^2$, then we have $p = n^2 - a^2 = (n - a)(n + a)$. If we take $n> 1$, then that cannot be prime unless $n-a = 1$ and $n + a$ is prime. We need only check the case $a = n - 1$, and check that $n + a$ is not prime.

Note that $n + a = 2n - 1$, so any $n$ where $2n - 1$ is not prime will do.

That gives us $n = 5, 8, 11, 13 \dots$ and examples $25, 64, 121, 169 \dots$.

PS I see @fresh_42 has already posted something like this.

 

[PeroK]

Also, the question does not explicitly say $a$ is an integer. You may be expected to also cover non-integer values of $a$.

$a$ must be an integer. Diophantine equations generally have real solutions. In this case, for any positive integer $n$ and any prime $p \le n$ we have the solution:
$$a = \sqrt{n - p}$$

 

[Steve4Physics]

$a$ must be an integer. Diophantine equations generally have real solutions. In this case, for any positive integer $n$ and any prime $p \le n$ we have the solution:
$$a = \sqrt{n - p}$$

Yes. IMO the original question is badly written. We are unambiguously told what $p$ is. But all we are told about $a$ is that $a\geq 0$.

The question, as stated, would allow, for example $a=\sqrt 2$. (But then the question wouldn't make sense.)

If I were answering, for completeness I would start by saying $a$ is assumed to be an integer. Or maybe I'm being pedantic.

 

[PeroK]

If I were answering, for completeness I would start by saying $a$ is assumed to be an integer. Or maybe I'm being pedantic.

The question is patently a Diophantine equation posted by someone who is studying number theory. It's not necessary to exclude real and complex numbers at every turn.

 

[PeroK]

Then we have 25=25+0^2
=24+1^2
=21+2^2
=16+3^2
=9+4^2
=0+5^2.
Note that none of 0, 9, 16, 21, 24 and 25 are prime numbers or 1.

As a challenge, can you find all six numbers less than 100 that fail the conjecture? You have 25 and 64 from the given analysis of square numbers. Can you find the other four?

 

[Math100]

As a challenge, can you find all six numbers less than 100 that fail the conjecture? You have 25 and 64 from the given analysis of square numbers. Can you find the other four?

I only found out that n=1 works besides 25 and 64.

 

[fresh_42]

I only found out that n=1 works besides 25 and 64.

$n=1=\underbrace{1}_{p}+\underbrace{0^2}_{a^2}$ can be written as required.

 

[PeroK]

I only found out that n=1 works besides 25 and 64.

Did you try $34$?

 

[Math100]

Did you try $34$?

No.

 

[fresh_42]

No.

You can use an Excel sheet to check (I think, haven't tried.)

 

[PeroK]

Or, write a Python program using a sieve technique. If you're studying number theory in 2022 I suggest the ability to write computer programs is a huge advantage.

 

[SammyS]

Did you try $34$?

Whether you you try n=34 or some other candidate as a counter example, try to be systematic.

To see if some integer, $n$ is a counterexample, begin with $a=0$ and increment $a$ by $1$ while $a^2<n$. For each value of $a$, compute $p_a$ where $p_a=n=a^2$.
For a given number $n$, if all $p_a$ are composite (Neither prime, nor 1), then you have found a counter example.

Furthermore, consider using as candidates for $n$, non-prime numbers of the form $n=3k+1$. . You should find that using such a number for $n$ will generate a list of values for $p_a$ in which 5 of every 6 entries is divisible by 2 or 3 (or both).