# Can anyone please review/verify/check this number theory proof?

Math100
Homework Statement:
Prove that if gcd(a, b)=1, then gcd(a+b, ab)=1.
Relevant Equations:
None.
Proof: Suppose for the sake of contradiction that gcd(a, b) \neq 1.
Then there exists a prime number k that divides both a+b and ab.
Note that k divides either a or b.
Since k divides a+b,
it follows that k divides b.
Thus, this is a contradiction because a and b are relatively prime.
Therefore, if gcd(a, b)=1, then gcd(a+b, ab)=1.

fresh_42

fishturtle1
Homework Statement:: Prove that if gcd(a, b)=1, then gcd(a+b, ab)=1.
Relevant Equations:: None.

Suppose for the sake of contradiction that gcd(a, b)\neq1.
Did you mean ##\gcd(a+b, ab) \neq 1##?

Homework Statement:: Prove that if gcd(a, b)=1, then gcd(a+b, ab)=1.
Relevant Equations:: None.

Note that k divides either a or b.
Since k divides a+b,
it follows that k divides b.
It looks like, WLOG, we assumed ##k## divides ##a##.

Everything else looks good to me.

Math100
Math100
Did you mean ##\gcd(a+b, ab) \neq 1##?

It looks like, WLOG, we assumed ##k## divides ##a##.

Everything else looks good to me.
Yes, it was meant as 'does not equal' sign from latex.

fishturtle1
Yes, it was meant as 'does not equal' sign from latex.
I meant that in the first line in OP, it reads "Suppose that for sake of contradiction that ##\gcd(a, b) \neq 1##." But in the proof, you are using the assumption that ##\gcd(a+b, ab) \neq 1##.

Math100
Math100
But where should I place the sentence of "Without the loss of generality..."?

fishturtle1
But where should I place the sentence of "Without the loss of generality..."?
Note that k divides a or b. Without loss of generality, assume k divides a.

Math100
Math100
Oh, I see what you meant. The first sentence in the proof should be: Suppose for the sake of contradiction that gcd(a+b, ab) \neq 1. Because for using proof of contradiction, it's (P is true, Q is false), am I right?

fishturtle1
fishturtle1
Oh, I see what you meant. The first sentence in the proof should be: Suppose for the sake of contradiction that gcd(a+b, ab) \neq 1. Because for using proof of contradiction, it's (P is true, Q is false), am I right?
Yes, you are correct!

Math100
Math100
Below is my revised proof for this problem:

Suppose for the sake of contradiction that gcd(a+b, ab) \neq 1.
Then there exists a prime number k that divides both a+b and ab.
Note that k divides a or b.
Without loss of generality,
we assume that k divides a.
Since k divides a+b,
it follows that k divides b.
Thus, this is a contradiction because a and b are relatively prime.
Therefore, if gcd(a, b)=1, then gcd(a+b, ab)=1.

QED

fishturtle1
Math100
Can anyone please review/verify/check my revised proof above?

Math100
@fishturtle1 , I think my proof is perfect now, given the fact that you upvoted my revised proof. Thank you for the help on this problem.

Staff Emeritus