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

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

marked as duplicate by Bill Dubuque elementary-number-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Apr 30 at 22:03

• Yes, that is true. Did you have a question though? – Eric Naslund Sep 17 '11 at 22:38
• 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. – Arturo Magidin Sep 17 '11 at 22:50
• $k = 1\times k = (a,b)(a,c) = (a(a,b,c),bc) = (a,bc)$. – Arturo Magidin Sep 17 '11 at 23:09
• Someone has voted to close this question as a duplicate of another question. But I do not see how this is a duplicate. – Srivatsan Sep 18 '11 at 3:43

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.

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

• 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. – Martin Sleziak Apr 11 '12 at 14:52