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.

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.

share|improve this question
2  
@nhru it is not quite so trivial as you make it sound, and the allusion to equivalence relations escapes me. –  Ittay Weiss Feb 12 at 1:25
1  
@nhru That's not the OP and, further, it is false, e.g. $\,(2,3)=1=(3,4)\,$ but $\,(2,4) = 2 > 1.\ \ $ –  Bill Dubuque Mar 2 at 22:23
    

7 Answers 7

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.

share|improve this answer
    
Unless the proof of Euclid's lemma uses this result with $a=p$. –  Aaron Meyerowitz Apr 9 at 16:02

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$

share|improve this answer
    
Would the downvoter care to comment? –  robjohn Feb 28 at 20:59
    
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$$ –  Bill Dubuque Mar 2 at 21:59
  • $\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...

share|improve this answer

More generally $\ (a,b)(a,c) = (aa,ab,ac,bc) = (a\color{#c00}{(a,b,c)},bc) = (a,bc)\ $ if $\ \color{#c00}{(a,b,c)=1},\ $ where we have applied basic gcd laws (associative, commutative, distributive).

share|improve this answer
1  
You are kind of assuming what you want to prove...(because now those rules need a proof) –  chubakueno Feb 12 at 2:22
    
@chubakueno Not true. Any proof of this will use prior results. But neither this proof (or others posted) "assume what you want to prove". –  Bill Dubuque Feb 12 at 2:28

Yet another answer...

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

share|improve this answer

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=au+cv $$ find $S,T$ with $$1=aS+(bc)T.$$ Multiplying by $1$ is a useful trick/technique for questions of this sort. $$1=au+cv=au+1cv=au+(as+bt)cv$$ so $$1=a(u+scv)+bc(tv).$$

What I like is that uses nothing more than basic properties of rings so the proof is applicable in many rings.

share|improve this answer

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

share|improve this answer

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.