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

Mentor
2022 Award
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
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.

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

• Math100
Math100
Here is another one: ##x^2+x+41## is always prime for ##x\in \mathbb{N},## true or not?
Yes, it's true.

Mentor
2022 Award
Yes, it's true.
Nope. It is not, but it takes some numbers until it is false. What about ##x=41##?

• Math100
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.

Mentor
2022 Award
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
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?

Mentor
2022 Award
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.

• Math100
Mentor
2022 Award
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
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.

Gold Member
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 ##..

• fresh_42
Homework Helper
Gold Member
2022 Award
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##.

• Math100
Mentor
2022 Award
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
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.

Mentor
2022 Award
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.

Last edited:
• Math100
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.

Homework Helper
Gold Member
2022 Award
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.

• Math100
Homework Helper
Gold Member
2022 Award
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}$$

Homework Helper
Gold Member
2022 Award
##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.

Homework Helper
Gold Member
2022 Award
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.

• Math100
Homework Helper
Gold Member
2022 Award
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.

Mentor
2022 Award
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.

Homework Helper
Gold Member
2022 Award
I only found out that n=1 works besides 25 and 64.
Did you try ##34##?

• SammyS
Math100
Did you try ##34##?
No.

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

• Math100
Homework Helper
Gold Member
2022 Award
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.

• sysprog
Staff Emeritus