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.

I know it might be too easy for you guys here. I'm practicing some problems in the textbook, but this one really drove me crazy.
From $\gcd( a, b ) = 1$, I have $ax + by = 1$, where should I go from here? The extra $ac$ is so annoying. Any hint?

Thanks,
Chan

share|improve this question
1  
Please try to use LaTeX instead of quote marks. –  Arturo Magidin Feb 7 '11 at 22:38
4  
@Arturo Magidin: I will try to learn how Latex when I have time. Thanks for your suggestion and again, your edit. –  Chan Feb 7 '11 at 22:40

6 Answers 6

up vote 16 down vote accepted

Let $d_1 = \gcd(c,b)$ and $d_2 = \gcd(ac,b)$.

So we have $cx_1 + by_1 = d_1$ and $acx_2 + by_2 = d_2$.

Further we have $ax + by = 1$.

Now multiply $ax+by = 1$ by $d_1$, write $d_1 = cx_1 + by_1$ and rearrange to show that $d_2|d_1$ i.e.

$d_1 \times (ax+by = 1) \Rightarrow ax(cx_1 + by_1) + bd_1y = d_1 \Rightarrow a c (x x_1) + b(a x y_1 + d_1 y) = d_1$. $d_2 = \gcd(ac,b)$ divides any integer linear combination of $ac$ and $b$ and hence $d_2 | d_1$

And by a similar argument multiply $ax+by = 1$ by $d_2$, write $d_2 = acx_2 + by_2$ and rearrange to show that $d_1|d_2$ i.e.

$d_2 \times (ax+by = 1) \Rightarrow ax(acx_2 + by_2) + bd_2y = d_2 \Rightarrow c (a^2 x x_2) + b(a x y_2 + d_2 y) = d_2$. $d_1 = \gcd(c,b)$ divides any integer linear combination of $c$ and $b$ and hence $d_1 | d_2$

So we have $d_1 | d_2$ and $d_2 | d_1$ and $d_1$,$d_2$ are non-negative since they are the gcd of two integers and hence $d_1 = d_2$

share|improve this answer
    
@Sivaram: Thanks for a very simple, and step by step proof ;) –  Chan Feb 7 '11 at 22:47
    
@Sivaram: nitpick: "So we have $d_1|d_2$ and $d_2|d_1$" and both nonnegative, "and hence $d_1=d_2$." –  Arturo Magidin Feb 7 '11 at 22:51
    
@Chan: This comment is more of a general comment. The above proof demonstrates the power of Euclidean algorithm. So many nice things happen in integers and some other rings because of the Euclidean algorithm (In fact these rings are termed Euclidean rings). en.wikipedia.org/wiki/Euclidean_domain –  user17762 Feb 7 '11 at 23:14
    
@Arturo: Edit done. –  user17762 Feb 7 '11 at 23:15
    
@Siv: Simplified it's $\rm\ (b,c)\ |\ b,ac\ \Rightarrow\ (b,a)\ |\ (b,ac)\:.\:$ Conversely $\rm\ (b,ac)\ |\ b,\: c=c(ax+by)\ \Rightarrow\ (b,ac)\ |\ (b,c)\:.\ $ **QED** $\ $ Here $\rm\ (b,ac)\ |\ (ac)\:x + (b)\:cy\ $ since $\rm\ (b,ac)\ |\ b,\: ac\ $ so it divides said sum. This uses a Bezout- form of the gcd distributive law. Generalizing yields $\rm\ (b,ac)\ |\ ac,bc\ \Rightarrow\ (b,ac)\ |\ (ac,bc) = (a,b)c\ $ $\rm [= c\ if\ (a,b) = 1]\:.\:$ This proof works in any gcd domain since it doesn't employ Bezout's law, i.e. $\rm\ gcd(a,b)\ $ is a linear combination of $\rm\:a,b\:$. See my post. –  Bill Dubuque Feb 19 '11 at 17:58

My attempt at a Bill Dubuquesque argument: \begin{align*} r|ac,\;b &\Longleftrightarrow r|ac,\;bc,\;b\\ &\Longleftrightarrow r|\gcd(ac,bc),\;b\\ &\Longleftrightarrow r|\gcd(a,b)c,\;b &\quad&\mbox{(since $\gcd(ac,bc)=\gcd(a,b)c$)}\\ &\Longleftrightarrow r|c,\;b \end{align*}

share|improve this answer
    
By trivial, you mean is it a theorem or defintion? Sorry I'm not a fast thinker :(, rather very slow. So could you slow down a little bit. –  Chan Feb 7 '11 at 22:43
    
@Chan: I changed it, but: if something divides $b$ and $c$, then it divides $b$ and any multiple of $c$, in particular $b$ and $ac$. So the greatest common divisor of $b$ and $c$ must divide the greatest common divisor of $b$ and $ac$. Remember that anything that divides $x$ and $y$ must divide $\gcd(x,y)$. –  Arturo Magidin Feb 7 '11 at 22:44
    
Thanks again. It will take me sometimes to understand it completely. –  Chan Feb 7 '11 at 22:47
3  
+1 for "Dubuquesque". (And because it's a clean proof.) –  ShreevatsaR Feb 8 '11 at 10:57

This follows easily from basic laws of GCD arithmetic. First I will present the proof using the standard notation $\rm\: (a,b)\:$ for $\rm\: gcd(a,b),\: $ immediately followed by a proof employing a more suggestive arithmetical notation, namely denoting $\rm\:\gcd(a,b)\:$ by $\rm\ a \dot+ b\:.\:$ Because the arithmetic of GCDs shares many of the same basic laws of the arithmetic of integers, the proof becomes more intuitive using a notation that highlights this common arithmetical structure. The proof employs only said basic GCD laws, namely the associative law, and the commutative law, combined with the fundamental distributive law $\rm\, \ (ac,bc)\ =\ (a,b)\:c\,\ $ and the GCD-specific law $\rm\: \color{#C00}{(c,1) = 1}.\: $

$\begin{eqnarray} \qquad\ &\rm (ac,\:b)\: &=&\rm\: (ac,b\:\color{#C00}{(c,1)})\: &=&\rm\: (ac,\:bc,\:b) &=&\rm\ ((a,b)\:c,b)\: &[\rm\: &=&\rm\: (c,\:b)\ &\rm if\ \ \ (a,b) &=&\rm 1\:] \\ &\rm ac \dot+ b &=&\rm\ ac \dot+ b\:\color{#C00}{(c \dot+ 1)} &=&\rm\,\ ac\dot+bc\dot+b &=&\rm\ (a\dot+b)\:c \dot+ b\ &[ &=&\rm\ \: c \dot+ b\ \:\ &\rm if\rm\quad a\dot+b &=&\rm 1\:] \end{eqnarray}$

Notice how the suggestive notation in the second proof invites us to exploit our well-honed arithmetical intuition regarding the associative, commutative and distributive laws of integer arithmetic during analogous GCD arithmetic proofs. $\ $ For a less trivial example see my similar proof of the Freshman's Dream $\rm\ (A,B)^n\, =\ (A^n,B^n)\ $ for GCDs and cancellable ideals.

The motivation behind this powerful abstract axiomatic approach becomes much clearer should you go on to study ideal theory and/or divisor theory (and you should, for there lies much beauty).

For further discussion and generalizations see this post and see my menagerie of posts on GCDs.

share|improve this answer
2  
+1 For this awesome proof. –  Ramana Venkata Nov 7 '12 at 8:10

Not sure if I can prove it algebraically but can try to explain logically. There is no common denominator between a and b (this is what gcd(a,b) = 1 means).

When you multiply a * c you introduce c's prime factors to the new number "ac".

So, if any new common factors (between ac and b) are introduced, we know that they came solely from c. We know this because prior to multiplying by c there were no common denominators. So, the only commonality that could originate here is from c and b.

share|improve this answer

(a,c)=1, so there are integers x,y such that ax+cy=1. (b,c)=1, so there are integers z,w such that bz+cw=1.

multiplying the two equations we get, axbz+axcw+cybz+cycw=1

simplifying our answer we have, ab(xz)+c(axw+yzb+ycw)=1.

it follows that (ab,c)=1.

share|improve this answer

We could prove the contrapositive: $\gcd(ac,b) \neq \gcd(c,b) \Longrightarrow \gcd(a,b) \neq 1$. Let $d = \gcd(ac,b)$ and $d' = \gcd(c,b)$. Now $d' < d$. So $d$ does not divide $c$ and $b$ and $d$ divides $ac$ and $b$. So $\gcd(a,b) \neq 1$.

share|improve this answer
    
Why do you think that implies $gcd(a,b)\ne 1$? –  Bill Dubuque Feb 19 '11 at 6:12

Your Answer

 
discard

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

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