3
$\begingroup$

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

  • 1
    Yes, that is true. Did you have a question though?2011-09-17
  • 0
    See [this](http://math.stackexchange.com/questions/62072/how-to-show-that-gcdab-n-1/62078#62078). 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.2011-09-17
  • 1
    $k = 1\times k = (a,b)(a,c) = (a(a,b,c),bc) = (a,bc)$.2011-09-17
  • 0
    Someone has voted to close this question as a duplicate of [another question](http://math.stackexchange.com/questions/62072/how-to-show-that-gcdab-n-1). But I do not see how this is a duplicate.2011-09-18

2 Answers 2

2

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.

1

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.$

  • 1
    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.2012-04-11