Can anyone please verify/review this counterexample?

  • Thread starter Math100
  • Start date
  • #1
Math100
676
180
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?
 

Answers and Replies

  • #2
fresh_42
Mentor
Insights Author
2022 Award
17,645
18,339
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##?
 
  • #3
Math100
676
180
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.
 
  • #4
fresh_42
Mentor
Insights Author
2022 Award
17,645
18,339
Here is another one: ##x^2+x+41## is always prime for ##x\in \mathbb{N},## true or not?
 
  • #5
Math100
676
180
Here is another one: ##x^2+x+41## is always prime for ##x\in \mathbb{N},## true or not?
Yes, it's true.
 
  • #6
fresh_42
Mentor
Insights Author
2022 Award
17,645
18,339
Yes, it's true.
Nope. It is not, but it takes some numbers until it is false. What about ##x=41##?
 
  • #7
Math100
676
180
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.
 
  • #8
fresh_42
Mentor
Insights Author
2022 Award
17,645
18,339
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!
 
  • #9
Math100
676
180
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.
 
  • #10
Math100
676
180
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?
 
  • #11
fresh_42
Mentor
Insights Author
2022 Award
17,645
18,339
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.
 
  • #12
fresh_42
Mentor
Insights Author
2022 Award
17,645
18,339
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.
 
  • #13
Math100
676
180
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.
 
  • #14
WWGD
Science Advisor
Gold Member
6,291
8,174
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 ##..
 
  • #15
Steve4Physics
Homework Helper
Gold Member
2022 Award
1,595
1,441
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##.
 
  • #16
fresh_42
Mentor
Insights Author
2022 Award
17,645
18,339
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.##
 
  • #17
Math100
676
180
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.
 
  • #18
fresh_42
Mentor
Insights Author
2022 Award
17,645
18,339
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:
  • #19
Math100
676
180
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.
 
  • #20
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2022 Award
23,784
15,399
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.
 
  • #21
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2022 Award
23,784
15,399
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}$$
 
  • #22
Steve4Physics
Homework Helper
Gold Member
2022 Award
1,595
1,441
##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.
 
  • #23
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2022 Award
23,784
15,399
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.
 
  • #24
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2022 Award
23,784
15,399
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?
 
  • #25
Math100
676
180
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.
 
  • #26
fresh_42
Mentor
Insights Author
2022 Award
17,645
18,339
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.
 
  • #27
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2022 Award
23,784
15,399
I only found out that n=1 works besides 25 and 64.
Did you try ##34##?
 
  • #30
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2022 Award
23,784
15,399
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.
 
  • #31
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,697
1,273
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).
 

Suggested for: Can anyone please verify/review this counterexample?

Replies
6
Views
580
  • Last Post
Replies
8
Views
314
  • Last Post
Replies
1
Views
322
Replies
4
Views
394
  • Last Post
Replies
4
Views
260
Replies
5
Views
257
Replies
2
Views
661
Replies
7
Views
424
Replies
1
Views
278
Replies
6
Views
345
Top