2
$\begingroup$

How to prove that if $a$ and $b$ are relatively prime, then $\gcd(a, c) = \gcd(ab,c)$?

How to make a connection between $(a,b)=1$ and $ab$? I have no idea.

$\endgroup$
  • 1
    $\begingroup$ Hmm...are you missing some hypotheses? Take $a=2$, $b=3$ and $c=3$. $\endgroup$ – Matt Apr 5 '13 at 5:34
  • 1
    $\begingroup$ You mean $\rm\:b,c\:$ coprime, or else you mean $\rm\:gcd(a,bc).\:$ My answer assumes the latter (swap $\rm\:a\:$ and $\rm\:c\:$ in my answer if you meant the former). $\endgroup$ – Math Gems Apr 5 '13 at 6:07
4
$\begingroup$

I presume the problem is $\rm\: \color{#C00}{(a,b)=1}\:\Rightarrow\: (a,bc) = (a,c),\:$ where $\rm\:(x,y) := gcd(x,y).\:$ One quick proof uses basic gcd laws: $\rm\,\ (a,bc) = (a,bc,ac) = (a,(bc,ac)) = (a,\color{#C00}{(b,a)}c) = (a,c)$.

Alternatively: if $\rm\:d\mid a\:$ then $\rm\:d\mid bc\iff d\mid bc,ac\iff d\mid (bc,ac)=\color{#C00}{(b,a)}c = c.\:$ So $\rm\:a,bc\:$ and $\rm\:a,c\:$ have equal sets $\rm\,D\,$ of common divisors $\rm\:d,\:$ so equal greatest common divisor (= max $\rm\,D$).

Remark $\ $ If desired, one can trade gcd laws for Bezout identities, e.g

$$\rm\:(a,b)=1\:\Rightarrow\:\exists\, j,k\in\Bbb Z\!:\ ja\!+\!kb=1\ \ \ so\ \ \ d\mid a,bc\:\Rightarrow\: d\mid (ja\!+\!kb)c = c\qquad $$

which trades the above use of the gcd distributive law for said Bezout identity. However, the proofs using the gcd laws work more generally (general gcd domains need not have linear (Bezout) gcds).

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Probably you mean $\gcd(a,c)=\gcd(a,bc)$. Here is a different solution from that of Math Gems.

The $\gcd(a,b)$ can be characterized as the minimum of the set $N_{a,b}=\{ax+by\in\mathbb N:x,y\in\mathbb Z\}$. Since $\gcd(a,b)=1\Rightarrow ax+by=1$ for some $x,y\in\mathbb Z$.
Now if $aw+bcz\in N_{a,bc}\Rightarrow aw+bcz\in N_{a,c}$ right?
Conversely if $as+ct=q\in N_{a,c}$ then multiplying with $ax+by=1$ we obtain $a(asx+bsy+ctx)+bcty=q$ therefore $as+ct=q=a(asx+bsy+ctx)+bcty\in N_{a,bc}$.
We conclude that $N_{a,c}=N_{a,bc}$ and therefore $\gcd(a,c)=\min N_{a,c}=\min N_{a,bc}=\gcd(a,bc)$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.