Suppose the gcd (a,b) = 1 and c divides a + b. Prove that gcd (a,c) = 1 = gcd (b,c)

Question

I am lost.

So far...

If $\gcd (a,b) = 1$, by Bezout's Formula

$ax + by = 1$

If $c|(a+b)$, then $cf = a+b$

Then,

$a (x-y) + cfy = 1$

$b(yx) + cfx = 1$

Am I on the right track? Any suggestions?

Answer 1

It is true that two nonzero integers $a$ and $b$ are relatively prime if and only if there are integers $x$ and $y$ with $ax+by=1$. With this in mind, your last equation gives the desired result.

Answer 2

Bezout's identity says that there exists two integers x and y such that ax+by = gcd(a,b). In addition, if you have some positive integer d, such that there exists integers x and y with ax+by=d, then it is not necessary that d = gcd(a,b). If d is the smallest positive integer for which you can find integers x and y with ax+by=d, then it is true that d=gcd(a,b). Since you have found integers such that bx+cy = 1, there can be no smaller positive integer than 1, and it follows that gcd(b,c)=1. The result follows similarly for gcd(a,c).

Answer 3

Perhaps it is easier to proceed this way: Let $k$ be a common factor of $a$ and $c$, say $a=kd$ and $c=ke$. (We want to show that $k=1$.) Since $a+b=cf$ for some integer $f$, we get that $$b=cf-a=kef-kd=k(ef-d),$$ so $k$ divides $b$, and therefore it is a common factor of $a$ and $b$. Since their only common factor is $1$, by assumption, it follows that $k=1$, as we wanted. Exactly the same argument gives that $b$ and $c$ must be relatively prime as well.

---

To address your argument: (There is a small typo in your last equation: $yx$ should be $y-x$.) The argument you give is correct, but it is not because Bezout's formula gives you an "if and only if":

If $ax+by=d$, then $akx+bky=kd$, so clearly, knowing that a linear combination of $a$ and $b$ equals $t$ does not mean that $t$ is the greatest common divisor of $a$ and $b$. What we get from Bezout's result is that $t$ is a multiple of $\mathrm{gcd}(a,b)$ – This is what the proof gives us: That any linear combination of $a,b$ is a multiple of their greatest common divisor, and this greatest common divisor is precisely the smallest positive integer that can be represented as a linear combination of $a$ and $b$.

In the specific case that $ax+by=1$, (but only in that case), we can indeed conclude that $a$ and $b$ are relatively prime, because the equation gives us that $\mathrm{gcd}(a,b)$ divides $1$, so we in fact have $\mathrm{gcd}(a,b)=1$.

Answer 4

If by contradiction, $(a,c)=(b,c)=m>1$ then $m|a,m|b$ and $m|c$, which means that there exist an $m>1$ that simultaneously divides both $a$ and $b$ which then implies that $gcd(a,b)\geq m$ which contradicts our assumption.

Answer 5

Note that $\gcd(a,b)$ has the following property:

For every $d$ such that $d\mid b$ and $d\mid a$, we must have $d\mid \gcd(a,b)$. In other words, every common divisor of $a$ and $b$ is a divisor of $\gcd(a,b)$

We are given $cf=a+b$. Let $d:=\gcd(a,c)$, then we can write: $$ d(c'f - a') = b $$ Where $a':=a/d$ and $c':=c/d$. Which means that $d\mid b$, and hence $d\mid\gcd(a,b)=1$. but that is only possible if $d=1$. A similar argument works for $\gcd(b,c)$.