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

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.
  • #1
750
199
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.
 
  • Like
Likes fresh_42
Physics news on Phys.org
  • #2
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.
 
  • Like
Likes Math100
  • #3
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.
 
  • #4
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##.
 
  • Like
Likes Math100
  • #5
But where should I place the sentence of "Without the loss of generality..."?
 
  • #6
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.
 
  • Like
Likes Math100
  • #7
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?
 
  • Like
Likes fishturtle1
  • #8
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!
 
  • Like
Likes Math100
  • #9
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
 
  • Like
Likes fishturtle1
  • #10
Can anyone please review/verify/check my revised proof above?
 
  • #11
@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.
 
  • #12
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)
 
  • Like
Likes Math100
  • #13
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.
 

Suggested for: Can anyone please review/verify/check this number theory proof?

Back
Top