3
$\begingroup$

This question already has an answer here:

If $a, b, c$ and $k$ be integers, $\gcd(a,b) = 1$ and $\gcd(a, c)=k$, then $\gcd (bc, a)=k$.

$\endgroup$

marked as duplicate by Bill Dubuque elementary-number-theory Apr 30 at 22:03

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Yes, that is true. Did you have a question though? $\endgroup$ – Eric Naslund Sep 17 '11 at 22:38
  • $\begingroup$ See this. Same idea works; or, replace $a$ and $c$ with $a/k$, $c/k$; then $\gcd(a/k,b) |\gcd(a,b) = 1$, so $\gcd(a/k,b)=1$, and you reduce to that case. $\endgroup$ – Arturo Magidin Sep 17 '11 at 22:50
  • 1
    $\begingroup$ $k = 1\times k = (a,b)(a,c) = (a(a,b,c),bc) = (a,bc)$. $\endgroup$ – Arturo Magidin Sep 17 '11 at 23:09
  • $\begingroup$ Someone has voted to close this question as a duplicate of another question. But I do not see how this is a duplicate. $\endgroup$ – Srivatsan Sep 18 '11 at 3:43
2
$\begingroup$

Hint $\rm\ \ (a,bc)\ =\ (a\:(1,c),bc)\ =\ (a,ac,bc)\ =\ (a,(a,b)\:c)\ \ [\:=\ (a,c)\ \ if\ \ (a,b)=1\ ] $

The above proof uses only basic gcd laws (associative, commutative, distributive) - see here.

Alternatively, if your prefer to use Bezout's identity, consider the following

$$\rm \begin{array}{rl} \rm (a,b)\:(a,c) &=&\rm (a\:(a,b,c),\:bc)\\ \Rightarrow\quad\rm (a,c) &=&\rm (a,\:bc)\quad if\quad (a,b)= 1 \end{array}\ \ $$

The first identity above can easily be recast into Bezout form,namely

$$\begin{eqnarray} \rm(b,\ a)\ \ \ &\rm\!\!\! (c,\ \ a)&=&\rm\ (bc,\ &\rm a\:(a\:,\ &\rm b\:,\ &\rm c))\qquad \\ \rm (br\!\!+\!\!as)\:&\rm(ct\!\!+\!\!au) &=&\rm\ \ bc\:(rt)\!\!+\!\!&\rm a\:(asu\!\!+\!\!&\rm bru\!\!+\!\!&\rm cst) \end{eqnarray}$$

For further discussion see my post here.

$\endgroup$
1
$\begingroup$

Since $gcd(a,b)=1$, there exist two integers $x$ and $y$ such that $$ax+by=1\tag{1}$$ Also $gcd (a,c)=k$, there exist two integers $x_{1}$ and $y_{1}$ such that $$ax_{1}+cy_{1}=k\tag{2}$$ Now multiplying $(1)$ and $(2)$ we get, $$a^{2}xx_{1}+acxy_{1}+bayx_{1}+bcyy_{1}=k$$ $$\Rightarrow a(axx_{1}+cxy_{1}+byx_{1})+bc(yy_{1})=k$$ It follows that $gcd(a,bc)=k.$

$\endgroup$
  • 1
    $\begingroup$ Actually, this only shows $\gcd(a,bc)\mid k$, but the other part, i.e. $k\mid\gcd(a,bc)$ is easy. BTW you can use \gcd in LaTeX. $\endgroup$ – Martin Sleziak Apr 11 '12 at 14:52