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.

This question already has an answer here:

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

share|improve this question

marked as duplicate by Zander, Ayman Hourieh, O.L., Daniel Rust, amWhy Jul 8 '13 at 22:40

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  
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
2  
The ã and the -em inflection on Existem clearly mark it as Portuguese. –  Brian M. Scott Jul 8 '13 at 18:38
1  
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
3  
@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

2 Answers 2

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$.
share|improve this answer

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

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.