# Number theory: if $(a,b)=1$, show that $(ac,b)=(c,b)$ [duplicate]

Mostre que, se $(a, b) = 1$, então $(a · c, b) = (c, b)$

Como posso fazer isso usando

$(a,b) = 1\implies$ Existem $m,n$ naturais tais que $am - bn = 1$

Tentative translation:

Show that if $(a,b)=1$, then $(ac,b)=(c,b)$.

How can this be done using

$(a,b)=1\implies$ there exist natural numbers $m,n$ such that $am-bn=1$?

-

## marked as duplicate by Zander, Ayman Hourieh, Start wearing purple, Dan Rust, amWhyJul 8 '13 at 22:40

It's in Portuguese. The translated content is as follows: Show that if $(a, b) = 1$, then $(ac,b) = (c,b)$. How do I show that $(a,b) = 1 \rightarrow$ there exists some natural numbers such that $am - bn = 1$? – NasuSama Jul 8 '13 at 18:38
Can someone read this? w3.math.uminho.pt/site/files/historicooutros/1617_Numeros.pdf – frogeyedpeas Jul 8 '13 at 18:38
The ã and the -em inflection on Existem clearly mark it as Portuguese. – Brian M. Scott Jul 8 '13 at 18:38
For this problem, you will need to apply division algorithm to get to $(ac,b)$ and then, to $(c,b)$. – NasuSama Jul 8 '13 at 18:39
@frogeyedpeas: it is OK to ask in any language. Someone will translate for you. Please see meta.math.stackexchange.com/a/1619/630 for more information. – Carl Mummert Jul 8 '13 at 18:45

HINT: It is easy to show that $(c,b)\mid(ac,b)$. To show that $(ac,b)\mid(c,b)$, let $d=(ac,b)$.
• Prove that $(a,d)=1$. (Use the fact that $d\mid b$.)
• Now use the fact that $d\mid ac$ to prove that $d\mid c$. Here is where you can use the fact that there are natural numbers $m$ and $n$ such that $am-dn=1$: multiply the equation by $c$.
Solve $am-bn=1$ and $cu-bv=(b,c)$. Then replace $u$ with $u\cdot 1=u\cdot(am-bn)$ and re-arrange. You should be able to get an expression $$(ac)X+bY=(b,c)$$