Can anyone please review/verify my proofs for gcd problem?

In summary, we have four cases where gcd(a, b)=1:- gcd(a+b, a-b)=1 or 2- gcd(2a+b, a+2b)=1 or 3- gcd(a+b, a^2+b^2)=1 or 2- gcd(a+b, a^2+b^2)=1 or 2
  • #1
Math100
756
204
Homework Statement
Assuming that gcd(a, b)=1, prove the following:
(a) gcd(a+b, a-b)=1 or 2.
[Hint: Let d=gcd(a+b, a-b) and show that d##\mid## 2a, d##\mid##2b, and thus that d##\leq##gcd(2a, 2b)=2 gcd(a, b).]
(b) gcd(2a+b, a+2b)=1 or 3.
(c) gcd(a+b, a^{2}+b^{2})=1 or 2.
[Hint: a^{2}+b^{2}=(a+b)(a-b)+2b^{2}.]
(d) gcd(a+b, a^{2}-ab+b^{2})=1 or 3.
[Hint: a^{2}-ab+b^{2}=(a+b)^{2}-3ab.]
Relevant Equations
None.
Proof: (a) Suppose that gcd(a, b)=1.
Let d=gcd(a+b, a-b).
By definition of the greatest common divisor,
we have that d##\mid##(a+b) and d##\mid##(a-b).
This means d##\mid##[(a+b)+(a-b)] and d##\mid##[(a+b)-(a-b)],
so we have d##\mid##2a and d##\mid##2b.
Note that d##\leq##gcd(2a, 2b)=2 gcd(a, b).
Since gcd(a, b)=1, it follows that 2 gcd(a, b)=2(1)=2.
Thus, d##\mid##2, which implies that d=1 or d=2.
Therefore, gcd(a+b, a-b)=1 or 2.
(b) Suppose that gcd(a, b)=1.
Let d=gcd(2a+b, a+2b).
By definition of the greatest common divisor,
we have that d##\mid##(2a+b) and d##\mid##(a+2b).
This means d##\mid##[2(2a+b)-(a+2b)] and d##\mid##[-(2a+b)+2(a+2b)],
so we have d##\mid##3a and d##\mid##3b.
Note that d##\leq##gcd(3a, 3b)=3 gcd(a, b).
Since gcd(a, b)=1, it follows that 3 gcd(a, b)=3(1)=3.
Thus, d##\mid##3, which implies that d=1 or d=3.
Therefore, gcd(2a+b, a+2b)=1 or 3.
(c) Suppose that gcd(a, b)=1.
Let d=gcd(a+b, a^{2}+b^{2}).
By definition of the greatest common divisor,
we have that d##\mid##(a+b) and d##\mid##(a^{2}+b^{2}).
This means d##\mid##[(a^{2}+b^{2})+(a^{2}-b^{2})] and d##\mid##[(a^{2}+b^{2})-(a^{2}-b^{2})],
so we have d##\mid##2a^{2} and d##\mid##2b^{2}.
Note that d##\leq##gcd(2a^{2}, 2b^{2})=2 gcd(a^{2}, b^{2}).
Since gcd(a, b)=1, it follows that gcd(a^{2}, b^{2})=1.
Thus, 2 gcd(a^{2}, b^{2})=2(1)=2, and so d##\mid##2,
which implies that d=1 or d=2.
Therefore, gcd(a+b, a^{2}+b^{2})=1 or 2.
(d) Suppose that gcd(a, b)=1.
Let d=gcd(a+b, a^{2}-ab+b^{2}).
By definition of the greatest common divisor,
we have that d##\mid##(a+b) and d##\mid##(a^{2}-ab+b^{2}).
This means d##\mid##[(a+b)^{2}-(a^{2}-ab+b^{2})], so we have d##\mid##3ab.
Note that each prime divisor k of d must divide either 3, a or b.
Thus, we have that d##\mid##[3a(a+b)-3ab] and d##\mid##[3b(a+b)-3ab],
so d##\mid##3a^{2} and d##\mid##3b^{2}.
Then we get d##\leq##gcd(3a^{2}, 3b^{2})=3 gcd(a^{2}, b^{2}).
Since gcd(a, b)=1, it follows that gcd(a^{2}, b^{2})=1.
Thus, 3 gcd(a^{2}, b^{2})=3(1)=3, and so d##\mid##3,
which implies that d=1 or d=3.
Therefore, gcd(a+b, a^{2}-ab+b^{2})=1 or 3.
 
Physics news on Phys.org
  • #2
Math100 said:
Homework Statement:: Assuming that gcd(a, b)=1, prove the following:
(a) gcd(a+b, a-b)=1 or 2.
[Hint: Let d=gcd(a+b, a-b) and show that d##\mid## 2a, d##\mid##2b, and thus that d##\leq##gcd(2a, 2b)=2 gcd(a, b).]
(b) gcd(2a+b, a+2b)=1 or 3.
(c) gcd(a+b, a^{2}+b^{2})=1 or 2.
[Hint: a^{2}+b^{2}=(a+b)(a-b)+2b^{2}.]
(d) gcd(a+b, a^{2}-ab+b^{2})=1 or 3.
[Hint: a^{2}-ab+b^{2}=(a+b)^{2}-3ab.]
Relevant Equations:: None.

Note that d≤gcd(3a, 3b)=3 gcd(a, b).
Since gcd(a, b)=1, it follows that 3 gcd(a, b)=3(1)=3.
Thus, d∣3, which implies that d=1 or d=3.
b) From the first and second line, we can conclude ##d \le 3##. But that doesn't imply ##d## divides ##3##. But this can be fixed by changing the first line to "Note that ##d## divides ##\gcd(3a,3b) = 3\gcd(a, b)##". You may want to make a similar change in a, c, d) even though it kind of works out in a) and c) case.

Math100 said:
Homework Statement:: Assuming that gcd(a, b)=1, prove the following:
(a) gcd(a+b, a-b)=1 or 2.
[Hint: Let d=gcd(a+b, a-b) and show that d##\mid## 2a, d##\mid##2b, and thus that d##\leq##gcd(2a, 2b)=2 gcd(a, b).]
(b) gcd(2a+b, a+2b)=1 or 3.
(c) gcd(a+b, a^{2}+b^{2})=1 or 2.
[Hint: a^{2}+b^{2}=(a+b)(a-b)+2b^{2}.]
(d) gcd(a+b, a^{2}-ab+b^{2})=1 or 3.
[Hint: a^{2}-ab+b^{2}=(a+b)^{2}-3ab.]
Relevant Equations:: None.

By definition of the greatest common divisor,
we have that d∣(a+b) and d∣(a^{2}+b^{2}).
This means d∣[(a^{2}+b^{2})+(a^{2}-b^{2})] and d∣[(a^{2}+b^{2})-(a^{2}-b^{2})]
c) Maybe I'm just being slow, but i think it would be helpful to include a line "Since ##d \vert (a+b)##, we have ##d \vert (a+b)(a-b) = a^2 - b^2##. Other than that, i think everything else is correct.
Math100 said:
Homework Statement:: Assuming that gcd(a, b)=1, prove the following:
(a) gcd(a+b, a-b)=1 or 2.
[Hint: Let d=gcd(a+b, a-b) and show that d##\mid## 2a, d##\mid##2b, and thus that d##\leq##gcd(2a, 2b)=2 gcd(a, b).]
(b) gcd(2a+b, a+2b)=1 or 3.
(c) gcd(a+b, a^{2}+b^{2})=1 or 2.
[Hint: a^{2}+b^{2}=(a+b)(a-b)+2b^{2}.]
(d) gcd(a+b, a^{2}-ab+b^{2})=1 or 3.
[Hint: a^{2}-ab+b^{2}=(a+b)^{2}-3ab.]
Relevant Equations:: None.

Note that each prime divisor k of d must divide either 3, a or b.
Thus, we have that d∣[3a(a+b)-3ab] and d∣[3b(a+b)-3ab]
d) I don't think the first line implies the second, i.e., if a prime ##p## divides ##b## but not ##a## or ##3##, then we have ##p## doesn't divide ##3a(a+b) - 3ab##. However, the second line is true since ##d \vert (a+b)## and ##d \vert 3ab##. Other than that, and changing ##d \le 3## to ##d \vert 3##, it looks good to me.
 
  • Like
Likes Math100
  • #3
I revised this problem, can you please review/verify to see if it's correct this time?

Proof:
(a) Suppose that gcd(a, b)=1.
Let d=gcd(a+b, a-b).
By definition of the greatest common divisor,
we have that d##\mid##(a+b) and d##\mid##(a-b).
This means d##\mid##[(a+b)+(a-b)] and d##\mid##[(a+b)-(a-b)],
so we have d##\mid##2a and d##\mid##2b.
Note that d divides gcd(2a, 2b)=2 gcd(a, b).
Since gcd(a, b)=1, it follows that 2 gcd(a, b)=2(1)=2.
Thus, d##\mid##2, which implies that d=1 or d=2.
Therefore, gcd(a+b, a-b)=1 or 2.
(b) Suppose that gcd(a, b)=1.
Let d=gcd(2a+b, a+2b).
By definition of the greatest common divisor,
we have that d##\mid##(2a+b) and d##\mid##(a+2b).
This means d##\mid##[2(2a+b)-(a+2b)] and d##\mid##[-(2a+b)+2(a+2b)],
so we have d##\mid##3a and d##\mid##3b.
Note that d divides gcd(3a, 3b)=3 gcd(a, b).
Since gcd(a, b)=1, it follows that 3 gcd(a, b)=3(1)=3.
Thus, d##\mid##3, which implies that d=1 or d=3.
Therefore, gcd(2a+b, a+2b)=1 or 3.
(c) Suppose that gcd(a, b)=1.
Let d=gcd(a+b, a^{2}+b^{2}).
By definition of the greatest common divisor,
we have that d##\mid##(a+b) and d##\mid##(a^{2}+b^{2}).
Since d##\mid##(a+b), we have d##\mid##(a+b)(a-b)=a^{2}-b^{2}.
This means d##\mid##[(a^{2}+b^{2})+(a^{2}-b^{2})] and d##\mid##[(a^{2}+b^{2})-(a^{2}-b^{2})],
so we have d##\mid##2a^{2} and d##\mid##2b^{2}.
Note that d divides gcd(2a^{2}, 2b^{2})=2 gcd(a^{2}, b^{2}).
Since gcd(a, b)=1, it follows that gcd(a^{2}, b^{2})=1.
Thus, 2 gcd(a^{2}, b^{2})=2(1)=2, and so d##\mid##2,
which implies that d=1 or d=2.
Therefore, gcd(a+b, a^{2}+b^{2})=1 or 2.
(d) Suppose that gcd(a, b)=1.
Let d=gcd(a+b, a^{2}-ab+b^{2}).
By definition of the greatest common divisor,
we have that d##\mid##(a+b) and d##\mid##(a^{2}-ab+b^{2}).
This means d##\mid##[(a+b)^{2}-(a^{2}-ab+b^{2})],
so we have d##\mid##3ab.
Now we have that d##\mid##[3a(a+b)-3ab] and d##\mid##[3b(a+b)-3ab],
so d##\mid##3a^{2} and d##\mid##3b^{2}.
Note that d divides gcd(3a^{2}, 3b^{2})=3 gcd(a^{2}, b^{2}).
Since gcd(a, b)=1, it follows that gcd(a^{2}, b^{2})=1.
Thus, 3 gcd(a^{2}, b^{2})=3(1)=3, and so d##\mid##3,
which implies that d=1 or d=3.
Therefore, gcd(a+b, a^{2}-ab+b^{2})=1 or 3.

I am so sorry for the late response of this problem. I was too busy in my workplace for the past two days. Now this problem is revised. Please leave any comment or feedback. I want to know if it's good or not.
 
  • Like
Likes fishturtle1
  • #4
Math100 said:
I revised this problem, can you please review/verify to see if it's correct this time?

Proof:
(a) Suppose that gcd(a, b)=1.
Let d=gcd(a+b, a-b).
By definition of the greatest common divisor,
we have that d##\mid##(a+b) and d##\mid##(a-b).
This means d##\mid##[(a+b)+(a-b)] and d##\mid##[(a+b)-(a-b)],
so we have d##\mid##2a and d##\mid##2b.
Note that d divides gcd(2a, 2b)=2 gcd(a, b).
Since gcd(a, b)=1, it follows that 2 gcd(a, b)=2(1)=2.
Thus, d##\mid##2, which implies that d=1 or d=2.
Therefore, gcd(a+b, a-b)=1 or 2.
(b) Suppose that gcd(a, b)=1.
Let d=gcd(2a+b, a+2b).
By definition of the greatest common divisor,
we have that d##\mid##(2a+b) and d##\mid##(a+2b).
This means d##\mid##[2(2a+b)-(a+2b)] and d##\mid##[-(2a+b)+2(a+2b)],
so we have d##\mid##3a and d##\mid##3b.
Note that d divides gcd(3a, 3b)=3 gcd(a, b).
Since gcd(a, b)=1, it follows that 3 gcd(a, b)=3(1)=3.
Thus, d##\mid##3, which implies that d=1 or d=3.
Therefore, gcd(2a+b, a+2b)=1 or 3.
(c) Suppose that gcd(a, b)=1.
Let d=gcd(a+b, a^{2}+b^{2}).
By definition of the greatest common divisor,
we have that d##\mid##(a+b) and d##\mid##(a^{2}+b^{2}).
Since d##\mid##(a+b), we have d##\mid##(a+b)(a-b)=a^{2}-b^{2}.
This means d##\mid##[(a^{2}+b^{2})+(a^{2}-b^{2})] and d##\mid##[(a^{2}+b^{2})-(a^{2}-b^{2})],
so we have d##\mid##2a^{2} and d##\mid##2b^{2}.
Note that d divides gcd(2a^{2}, 2b^{2})=2 gcd(a^{2}, b^{2}).
Since gcd(a, b)=1, it follows that gcd(a^{2}, b^{2})=1.
Thus, 2 gcd(a^{2}, b^{2})=2(1)=2, and so d##\mid##2,
which implies that d=1 or d=2.
Therefore, gcd(a+b, a^{2}+b^{2})=1 or 2.
(d) Suppose that gcd(a, b)=1.
Let d=gcd(a+b, a^{2}-ab+b^{2}).
By definition of the greatest common divisor,
we have that d##\mid##(a+b) and d##\mid##(a^{2}-ab+b^{2}).
This means d##\mid##[(a+b)^{2}-(a^{2}-ab+b^{2})],
so we have d##\mid##3ab.
Now we have that d##\mid##[3a(a+b)-3ab] and d##\mid##[3b(a+b)-3ab],
so d##\mid##3a^{2} and d##\mid##3b^{2}.
Note that d divides gcd(3a^{2}, 3b^{2})=3 gcd(a^{2}, b^{2}).
Since gcd(a, b)=1, it follows that gcd(a^{2}, b^{2})=1.
Thus, 3 gcd(a^{2}, b^{2})=3(1)=3, and so d##\mid##3,
which implies that d=1 or d=3.
Therefore, gcd(a+b, a^{2}-ab+b^{2})=1 or 3.

I am so sorry for the late response of this problem. I was too busy in my workplace for the past two days. Now this problem is revised. Please leave any comment or feedback. I want to know if it's good or not.
No need to apologize; the proofs look correct to me.
 
  • Like
Likes Math100
  • #5
Thank you so much for the help!
 

Related to Can anyone please review/verify my proofs for gcd problem?

1. What is the purpose of having someone review/verify my proofs for gcd problem?

The purpose of having someone review/verify your proofs for gcd problem is to ensure the accuracy and validity of your work. It is always beneficial to have a fresh set of eyes look over your proofs to catch any potential errors or offer suggestions for improvement.

2. Who is qualified to review/verify my proofs for gcd problem?

Ideally, someone who is knowledgeable and experienced in the field of mathematics and specifically in gcd problems would be the most qualified to review/verify your proofs. This could be a fellow scientist, a professor, or a peer with a strong understanding of the subject matter.

3. How do I know if my proofs for gcd problem are correct?

One way to determine the correctness of your proofs for gcd problem is to have them reviewed and verified by someone else. You can also check your work against established theorems and principles in the field of mathematics to see if your proofs align with existing knowledge.

4. Should I have my proofs for gcd problem reviewed before or after submission for publication?

It is always a good idea to have your proofs for gcd problem reviewed before submission for publication. This will give you the opportunity to make any necessary revisions or improvements before your work is published.

5. Is it acceptable to have multiple people review/verify my proofs for gcd problem?

Yes, it is acceptable to have multiple people review/verify your proofs for gcd problem. In fact, having multiple perspectives can be beneficial in catching any errors or offering different insights. However, it is important to make sure that all reviewers are qualified and their feedback is properly considered.

Similar threads

  • Calculus and Beyond Homework Help
Replies
2
Views
997
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
7
Views
2K
  • Calculus and Beyond Homework Help
Replies
12
Views
1K
  • Calculus and Beyond Homework Help
Replies
20
Views
2K
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Precalculus Mathematics Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
19
Views
2K
Back
Top