Proof that gcd(a+b, ab) = 1 when gcd(a, b) = 1

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

 

[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]

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]

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]

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]

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

 

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

 

[Office_Shredder]

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]

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.