Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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
Setup: Let $d_1 = \gcd(c,b)$ and $d_2 = \gcd(ac,b)$.
So we have $cx_1 + by_1 = d_1$, $acx_2 + by_2 = d_2$, and $ax + by = 1$ by Bezout.
Step 1: Multiply $ax+by = 1$ by $d_1$ (using $d_1 := cx_1 + by_1$) and rearrange to show that $d_2|d_1$.
$$\begin{aligned} d_1 (ax+by &= 1)\\ \implies ax(cx_1 + by_1) + bd_1y &= d_1 \\ \implies a c (x x_1) + b(a x y_1 + d_1 y) &= d_1 \end{aligned}$$
Since we know that $d_2 = \gcd(ac,b)$ divides any integer linear combination of $ac$ and $b$, we have $d_2 | d_1$.
Step 2: By a similar argument, multiply $ax+by = 1$ by $d_2$ (using $d_2 := acx_2 + by_2$) and rearrange to show that $d_1|d_2$.
$$\begin{aligned} d_2 (ax+by &= 1) \\ \implies ax(acx_2 + by_2) + bd_2y &= d_2 \\ \implies c (a^2 x x_2) + b(a x y_2 + d_2 y) &= d_2 \end{aligned}$$
Since we know that $d_1 = \gcd(c,b)$ divides any integer linear combination of $c$ and $b$, we have $d_1 | d_2$.
Conclusion: Finally, because we have $d_1 | d_2$, $d_2 | d_1$, and $d_1$ and $d_2$ are non-negative (since they are the gcd of two integers), we conclude that $d_1 = d_2$. Thus, $gcd(ac,b)=gcd(c,b)$.
This form of Euclid's Lemma 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, 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 below uses only said basic GCD laws: the associative law, $ $ the commutative law, the distributive law $\rm\, (a,b)c = (ac,bc)\, $ and the GCD-specific law $\rm\: \color{#C00}{(c,1) = 1}.\: $
Lemma $\rm \ \ (ac,b) = ((a,b)c,b)\,\ [=\, (c,b)\ \ {\bf if}\ \ (a,b)=1]$
$\begin{align}\rm {\bf Proof}\ \ \ ((a,\,b)c,\ b) &\rm =\, (ac,\,bc,\,b) = (ac,\ b\color{#c00}{(c,\ 1)}) = (ac,b)\\[.3em] \rm (a\dot+b)c\dot+b\ \:\! &\rm =\,\ ac\dot+bc\dot+b\, = \ \, ac\dot+b\color{#c00}{(c\dot+1)}\ =\ ac\dot+b \end{align}$
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 a 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.
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*}
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.
(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.
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$.
Use the GCD in prime factorization form.
If $m = \prod p_i ^ {m_i}, n = \prod p_i^{n_i}$, then $ d = \prod p_i^{\min(m_i, n_i)}$.
The result follows by showing that
$$ \min (m_i, n_i + k_i) = \min (m_i, \min (m_i, n_i) + k_i)$$
A direct way of showing this is to condition on $ m_i \geq n_i$ (so $\min(m_i, n_i) = n_i$) and $ m_i < n_i$ (so both sides equal $m_i$).
