Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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
1  
$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
add comment

2 Answers

HINT $\rm\quad (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.

share|improve this answer
add comment

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

share|improve this answer
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. –  Martin Sleziak Apr 11 '12 at 14:52
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.