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

• Math100
I will keep that in mind. Thanks again for the help and verification!In summary, we prove that if gcd(a, b)=1, then gcd(a+b, ab)=1 by assuming the opposite and using proof by contradiction. We show that if gcd(a+b, ab) is not equal to 1, then there exists a prime number k that divides both a+b and ab. By assuming that k divides a, we show that it also divides b, leading to a contradiction because a and b are relatively prime. Therefore, our initial assumption is false and the statement is proven.

#### 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
Math100 said:
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##?

Math100 said:
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
fishturtle1 said:
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.

Math100 said:
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
But where should I place the sentence of "Without the loss of generality..."?

Math100 said:
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
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
Math100 said:
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
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
Can anyone please review/verify/check my revised proof above?

@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.

This looks good to me. Note if you put two # signs on each side of your math formulas, it will render as tex so \neq becomes ##\neq## (try quoting other people's posts to see what it looks like if you still aren't sure)

Math100
Office_Shredder said:
This looks good to me. Note if you put two # signs on each side of your math formulas, it will render as tex so \neq becomes ##\neq## (try quoting other people's posts to see what it looks like if you still aren't sure)
Okay, thank you.