How do I go about proving this?
If $\gcd(a,b)=1$ and $\gcd(a,c)=1$, then $\gcd(a,bc)=1$. I'm very confused with gcd proofs.
$\begingroup$
$\endgroup$
2
-
$\begingroup$ See also math.stackexchange.com/questions/485013/… $\endgroup$– Martin SleziakSep 28, 2014 at 7:14
-
$\begingroup$ A few more related posts: How to show that $\gcd(ab,n)=1$ if $\gcd(a,n)=\gcd(b,n)=1$?, Prove that if $\gcd(a,c)=1$ and $\gcd(b,c)=1$ then $\gcd(ab,c)=1$, If $\gcd(a,n) = 1$ and $\gcd(b,n) = 1$, then $\gcd(ab,n) = 1$.. $\endgroup$– Martin SleziakMay 3, 2019 at 12:19
Add a comment
|
7 Answers
$\begingroup$
$\endgroup$
7
Using Bezout's Identity:
Since there are $x,y,u,v$ so that $\color{#C00000}{ax+by=1}$ and $\color{#00A000}{au+cv=1}$, we have $$ \begin{align} \color{#C00000}{by}\color{#00A000}{cv} &=\color{#C00000}{(1-ax)}\color{#00A000}{(1-au)}\\ &=1-a(x+u-axu)\\ \color{#0000FF}{a}(x+u-axu)+\color{#0000FF}{bc}vy &=1 \end{align} $$ Therefore, $(\color{#0000FF}{a},\color{#0000FF}{bc})=1$
-
$\begingroup$ I too am curious about the downvote. Btw, why do you rearrange before multiplying the Bezout identities? Perhaps to highlight the interpretation in terms of unit multiplicativity? $ $ i.e. $$\,{\rm mod}\ a\!:\ \ \color{#c00}by\equiv 1\equiv \color{#c00}cv\,\Rightarrow \color{#c00}{bc}yv\equiv 1,\ \ \ {\rm i.e.}\ \ \color{#c00}{b,c}\ \ {\rm unit}\ \Rightarrow\, \color{#c00}{bc}\ \ \rm unit$$ $\endgroup$ Mar 2, 2014 at 21:59
-
$\begingroup$ How does $a(x+u-axu)+bcvy=1\implies (a,bc)=1$? $\endgroup$– WitikoJun 9, 2015 at 14:57
-
1$\begingroup$ @Witiko: since it is a linear combination of $a$ and $bc$ that equals $1$. If $a$ and $bc$ had a common factor, that common factor would divide any linear combination of $a$ and $bc$. $\endgroup$– robjohn ♦Jun 9, 2015 at 16:33
-
$\begingroup$ @robjohn I only have a question about the final line. So I understand that to get 1-a(x+u-axu) we simply factored out an a. Then we can move the a term to the other side in an attempt to show we have a linear combination of a and bc equal to 1. However where did the +bcvy come from? $\endgroup$– LilOct 29, 2019 at 16:22
-
$\begingroup$ @Lil: each line follows from the one before, and the first line is color coded to the appropriate Bezout identity. The $bcvy$ is simply brought down from the $bycv$ on the line above. $\endgroup$– robjohn ♦Oct 29, 2019 at 17:45
$\begingroup$
$\endgroup$
1
If you know Euclid's Lemma (if $p$ is a prime number and $p$ divides the product $bc$, then either $p$ divides $b$ or $p$ divides $c$), then you can proceed as follows. Let $d=gcd(a,bc)$ and assume, to arrive at a contradiction, that $d>1$. Let $p$ then be a prime number dividing $d$. Then $p$ divides both $a$ and $bc$, and thus either $p$ divides $b$ or it divides $c$. If $p$ divides $b$, then since it also divides $a$, it follows that $p$ divides $gcd(a,b)=1$, which is absurd. Similarly, $p$ dividing $c$ leads to a contradiction.
Remark: this solution avoids considering the entire prime number decomposition for the given numbers. I find it to be a nice little trick that produces clean proofs.
answered Feb 12, 2014 at 1:25
-
$\begingroup$ Unless the proof of Euclid's lemma uses this result with $a=p$. $\endgroup$ Apr 9, 2014 at 16:02
$\begingroup$
$\endgroup$
1
We can take as the definition of "$a,b$ are relatively prime" that there are $s,t$ with $1=as+bt$. Then the question becomes: given that$$1=as+bt$$and$$1=as^\prime+ct^\prime$$find $S,T$ with$$1=aS+(bc)T.$$Multiplying by $1$ is a useful trick/technique for questions of this sort.$$1=as+bt=as+\mathbf{1}bt=as+\mathbf{(as^\prime+ct^\prime)}bt$$so$$\begin{align}1&=a(s+cst^\prime)+bc(tt^\prime)\\&=a(s^\prime+bs^\prime t)+bc(tt^\prime).\end{align}$$
The second formula arises from the first by applying $(bc)(ss^\prime)(tt^\prime)$ or shifting the derivation. A single formula invariant under that permutation is
$$1=(as+bt)(as^\prime+ct^\prime)=a(ass^\prime+bts^\prime+cst^\prime)+bc(tt^\prime).$$
The symmetry is nice but the first formulas are smaller.
What I like is that uses nothing more than basic properties of rings so the proof is applicable in many rings.
-
1$\begingroup$ The definition of "$a,b$ are relatively prime" is different. If $a,b$ are relatively prime / coprime / co-prime, i.e. $\gcd(a,b)=1$ (greatest common divisor), then by Bézout identity/lemma it follows that there exist $s,t\in\mathbb Z$ such that $as+bt=1$. $\endgroup$ Sep 12, 2017 at 14:18
$\begingroup$
$\endgroup$
3
More generally $\ \bbox[5px,border:1px solid #c00]{(a,b)(a,c) = (a,bc)}\ $ if $\ \color{#0a0}{(a,b,c)=1},\, $ follows by expanding the product, i.e. $\ (a,b)(a,c) = (aa,ab,ac,bc) = (a\color{#0a0}{(a,b,c)},bc) = (a,bc),\, $ using GCD polynomial arithmetic, i.e. the GCD associative, commutative, and distributive laws (explained in the prior link).
OP is special case $\ (a,b)\! =\! \color{#c00}{\bf 1}\! =\! (a,c),\ $ so $\,\color{#0a0}{(a,b,c)\! =\! 1},\ $ so $\ \color{#c00}{\bf 1\cdot 1} = (a,bc)\ $ by above.
Remark $ $ Worth emphasis: the common Bezout-based proofs can be viewed more conceptually as: invertibles are closed under product, via $\,b,c\,$ are coprime to $\,a\!\iff\! b,c\,$ invertible $\!\bmod a,\,$ by Bezout. The proof is obvious: $\,\overset{}{bb'}\equiv 1\equiv cc'\Rightarrow\ bc\,\color{#c00}{c'b'}\equiv 1\, $ (i.e. $\,(bc)^{-1}\equiv \color{#c00}{c^{-1} b^{-1}})$.
In fraction language it's obvious $\,1/(bc) \equiv (1/b)(1/c).\,$ So the proof becomes obvious and intuitive after translating the Bezout equations into more arithmetical congruence language - being essentially the same as well known inverse or fraction laws.
The above proof by GCD laws is more general than proofs using Bezout's linear gcd reprentation, since generally gcds fails to have this form, e.g. in the UFD $\rm\,D = \mathbb Q[x,y]\,$ of polynomials in $\rm\,x,y\,$ with rational coefficients we have $\rm\,gcd(x,y) = 1\,$ but there are no $\rm\,f(x,y),\, g(x,y)\in D\,$ such that $\rm\,x\,f(x,y) + y\,g(x,y) = 1;\,$ indeed, if so, then evaluating the purported Bezout equation at $\rm\:x = 0 = y\:$ yields $\,0 = 1.\,$ Similarly for $\,\gcd(2,x)=1\,$ in the UFD $\rm\,\Bbb Z[x]$.
Further, such GCD arithmetic is simpler than Bezout equation manipulations since it is essentially the same as (high-school) polynomial arithmetic - as explained in the first link above.
answered Feb 12, 2014 at 2:14
-
1$\begingroup$ You are kind of assuming what you want to prove...(because now those rules need a proof) $\endgroup$ Feb 12, 2014 at 2:22
-
$\begingroup$ @chubakueno Not true. Any proof of this will use prior results. But neither this proof (or others posted) "assume what you want to prove". $\endgroup$ Feb 12, 2014 at 2:28
-
$\begingroup$ To dismiss the purported circularity claim, notice the the linked proofs of the GCD arithmetic laws use only the GCD Universal Property $\,c\mid a,b\iff c\mid\gcd(a,b),\,$ which is proved there (in $\,\Bbb Z)\,$ using only the GCD Bezout equation (or it can be proved directly by induction using the Division algorithm, i.e. Euclidean descent). This property is actually the definition of the GCD in more general number systems (GCD domains). All the basic properties of the GCD follow from this. $\endgroup$ Oct 11, 2020 at 7:26
$\begingroup$
$\endgroup$
Since $a, b$ are relatively prime, there exist integers $x, y$ such that $ax + by = 1$. Multiplying both sides of this equation by $c$, we get $$acx + bcy = c.$$ Letting $d = \gcd(a, bc)$, we see from the equation above that since $d$ is a common divisor of $a$ and $bc$, $d$ also divides $c$ by linearity. Then, since every common divisor of two integers also divides their gcd, $d|\gcd(a, c)$. But $\gcd(a, c) = 1$, so $d$ divides $1$. Because the gcd is nonnegative, it follows that $d = \gcd(a, bc) = 1$.
$\begingroup$
$\endgroup$
- $\gcd(a,b)=1$ means what about the prime factors common to both $a,b$?
- same for $\gcd(a,c)$
- what is the prime decomposition of $bc$ if you know what $b$, $c$ decompose as?
Combine all together...
$\begingroup$
$\endgroup$
$\gcd(a,b)$ means a and b are relatively prime, this means, there is no other common factor other than 1.
you also know that $$\gcd(a,b) = 2^{\min(a_1,b_1)}.3^{\min(a_2,b_2)}.5^{\min(a_3,b_3)}...$$
Now the 2 equations already imply that $$\min(a_1,b_1) = \min(a_2,b_2)=...= 0$$ (there is no common factor of primes)
also $$\min(a_1,c_1) =\min(a_2,c_2)=... = 0$$
this imply, $$\min(a_1,b_1+c_1)= \min(a_2,b_2+c_2)=...=0$$ as the powers > 0, and adding them cannot be < 0,
This imply a,bc are also relatively prime, hence $$\gcd(a,bc)=2^{\min(a_1,b_1+c_1)}.3^{\min(a_2,b_2+c_2)}...= 1$$
($\min(a,b)$ represents here minimum value of a,b)
