Question 1068315: I do not even know where to start with this proof.
Prove or disprove: let a, b, and c be integers such that a and b are relatively prime and c divides a+b. Prove that gcd(a,c)=gcd(b,c)=1.
Answer by ikleyn(52879)   (Show Source):
You can put this solution on YOUR website! .
I do not even know where to start with this proof.
Prove or disprove: let a, b, and c be integers such that a and b are relatively prime and c divides a+b. Prove that gcd(a,c)=gcd(b,c)=1.
~~~~~~~~~~~~~~~~~~
I will prove the firs statement gcd(a,c) = 1, leaving the second to you.
Let assume that GCD(a,c) = d > 1. (GCD is the Greatest Common Divisor).
Then d divides both "a" and "c". (*)
Since "c" divides a+b, then "d" divides a+b too. (**)
Now, we have that "d" divides "a" (Line *) and "d" divides a+b (Line **).
It implies that "d" divides both "a" and "b".
It contradicts to the given fact that "a" and "b" are relatively simple.
Hence, the initial assumption GCD(a,c) = d > 1 is WRONG.
It means GCD(a,c) = 1.
When solving such problems, the major move is to make the first step.
|
|
|
