Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

marked as duplicate by Zander, Ayman Hourieh, Start wearing purple, Dan 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.

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

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