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

  • Thread starter Math100
  • Start date
  • #1
Math100
676
180
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.
 

Answers and Replies

  • #2
fishturtle1
394
81
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.
 
  • #3
Math100
676
180
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
fishturtle1
394
81
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##.
 
  • #5
Math100
676
180
But where should I place the sentence of "Without the loss of generality..."?
 
  • #6
fishturtle1
394
81
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.
 
  • #7
Math100
676
180
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
fishturtle1
394
81
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!
 
  • #9
Math100
676
180
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
Math100
676
180
Can anyone please review/verify/check my revised proof above?
 
  • #11
Math100
676
180
@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
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
5,461
1,391
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)
 
  • #13
Math100
676
180
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?

Replies
5
Views
561
Replies
7
Views
526
Replies
7
Views
547
Replies
5
Views
359
Replies
2
Views
414
Replies
2
Views
401
Replies
4
Views
374
Replies
2
Views
624
Top