# If $\gcd(a,b)= 1$ and $a$ divides $bc$ then $a$ divides $c\$ [Euclid's Lemma]

Well I thought this is obvious. since $\gcd(a,b)=1$, then we have that $a$ does not divide $b$ AND $a$ divides $bc$. this implies that $a$ divides $c$. done. but apparently this is wrong. help explain why this way is wrong please.

the question tells you give me two relatively prime numbers $a$ and $b$ such that $a$ divides the product $bc$, prove that $a$ divides $c$. how is this not obvious? explain to me how my "proof" is not correct.

• obvious is a very deadly word! try thinking of this in terms of prime factorisations, or use Bézout's lemma: en.wikipedia.org/wiki/B%C3%A9zout's_identity – citedcorpse Jun 11 '13 at 14:16
• The two statements "a does not divide b" and "a divides bc" do not suffice to imply that a divides c. For example, if a=6, b=4, and c=9, then both of the statements "a does not divide b" and "a divides bc" are true, yet a does not divide c. – Andreas Blass Jun 11 '13 at 14:39
• there can be no counterexample to the statement itself (we have provided two proofs that it is true). we're trying to provide a counterexample to the reasoning. your argument kind of jumps to the conclusion – citedcorpse Jun 11 '13 at 15:03
• In your question, you wrote "this implies that $a$ divides $c$." If "this" refers to the immediately preceding statement (which would be the obvious reading of what you wrote), namely "$a$ does not divide $b$ AND $a$ divides $bc$", then my counterexample shows that your statement is wrong. If, on the other hand, "this" includes also the assumption gcd$(a,b)=1$, then your statement is true but is just asserting what you should be proving (and the part "$a$ does not divide $b$" is redundant). – Andreas Blass Jun 11 '13 at 16:00
• Your inference $\ (a,b) = 1\,\Rightarrow a\nmid b\$ is true if $\,a > 1.\,$ However, it is of little use in proving the sought result. For us to debug your logic, you need to tell us precisely how you inferred that $\, a\mid c.$ What properties or laws of integer arithmetic did you employ? – Key Ideas Jun 11 '13 at 16:00

## 7 Answers

By Bézout's theorem and since $\gcd(a,b)=1$ then there's $u,v\in\mathbb Z$ s.t. $$ua+vb=1\tag{1}$$ we multiply $(1)$ by $c$ we find $$uac+vbc=c$$ now $a$ divide $uac$ and divide $vbc$ so $a$ divide their sum $c$.

• you just repeated what someone already said, i want to know why my way of doing this problem is wrong. – mathworld Jun 11 '13 at 14:25
• @mathworld look $4$ doesn't divide $6$ and divide $6\times 2$ so can you explain why $4$ doesn't divide $2$? – user63181 Jun 11 '13 at 14:31
• but you have to start with numbers that are relatively prime and you didnt. the question tells you give me two relatively prime numbers a and b such that a divides the product bc, prove that a divides c. by starting with 4 and 6, you did not start with relatively prime numbers. – mathworld Jun 11 '13 at 14:35
• If somebody wants to know the importance of being the two numbers relatively prime so how we convince him? – user63181 Jun 11 '13 at 14:37

Since $\gcd(a,b) = 1$, you can choose integers $x$ and $y$ so that $ax + by = 1$. Hence, $axc + byc = c$. Suppose $a| bc$; write $aq = bc$. Then $c = axc + yaq$, so $a|c$.

• yes i know this already but why is my way of doing this problem wrong? – mathworld Jun 11 '13 at 14:21
• YOu are assuming the result you wish to conclude as "obvious." It is not and I supply the reason it works. – ncmathsadist Jun 11 '13 at 14:24
• but if a divides the product bc and a does not divide b because of gcd(a,b)=1 , then the only thing left is for a to divide c. its as simple as that. can you find a counterexample of this? i do not think you can – mathworld Jun 11 '13 at 14:28
• it's difficult to find counterexamples when the result is true. what if $a = 4, b = 2$, and $c = 2$? where specifically have you used the fact that the $\gcd$ is exactly one? – citedcorpse Jun 11 '13 at 14:32
• then you didnt start with relatively prime a and b. and the question tells you to start with relatively primes a and b to show that if a divides bc, then a has to divide c – mathworld Jun 11 '13 at 14:36

Your reasoning is wrong for the following reason:

You say that

we have that $a$ does not divide $b$ AND $a$ divides $bc$ .

From here is conclude that $a|c$. This part is wrong. It is possible to have $a$ does not divide $b$ AND $a$ divides $bc$, but $a$ doesnot divide $c$.

For example $a=4, b=6$ and $c=2$.

• my reasoning is "we have gcd(a,b) =1 and a divides bc. then we have that a does not divide b AND a divides bc." therefore a divides c – mathworld Jun 11 '13 at 15:36
• @mathworld "therefore" is the wrong part. $4$ divides $6 \times 2$ and $4$ doesn't divide $6$. Can you conclude that $4$ divides $2$? – N. S. Jun 11 '13 at 15:43
• you ignore the fact that i said you start with two numbers relatively prime – mathworld Jun 11 '13 at 15:58
• @mathworld "we have that $a$ does not divide $b$ AND $a$ divides $bc$ . this implies that $a$ divides $c$ . done", I don't see you using the relatively prime for this part of the argument, and my example shows that this part of reasoning is wrong... Even if you reach the right conclusion, if part of the argument is flawed, the proof is wrong.... – N. S. Jun 11 '13 at 16:16

Your argument goes as follows: 1. Since $\gcd(a,b)=1$, then $a\nmid b$. That is correct. 2. You are given that $a\mid bc$.

From those two facts (that $a\nmid b$ and $a\mid bc$) you conclude that $a\mid c$. You give no reason for that conclusion. If you did not use again the fact that $\gcd(a,b)=1$, then your reasoning to conclude that $a\mid c$ must be wrong. That is, the fact that $a\mid c$ does not follow solely from the two facts that $a\nmid b$ and $a\mid bc$.

A good way of understanding whether when you said "this is obvious" it really was or not is to consider some cases where $a\nmid b$ and $a\mid bc$. Several of the other answers provide such cases, showing that the condition $\gcd(a,b)=1$ really is required.

Finally, if it really is obvious to you, you should be able to write it down formally. If you can't do that, then it probably isn't obvious. You'll find when you try to write it down, that you will need the fact that $\gcd(a,b)=1$. (Hint: look at the prime factorizations of $a$, $b$, and $c$).

The alternate method is to think of the gcd in terms of prime factorisation. Saying $\gcd(a,b) = 1$ is the same as saying $a$ and $b$ have no primes in their factorisations in common. Primes are characterised as the natural numbers $p$ such that if $p$ divides $ab$, then $p$ divides $a$ or $p$ divides $b$. Hopefully you can finish this from here.

• yes so then if a and b have different primes and the primes of a divide the primes of bc, since a and b have no primes in common, the primes in the product bc have to come from c. therefore a divides c. – mathworld Jun 11 '13 at 14:30

It seems you have in mind a proof that uses prime factorizations, i.e. the prime factors of $\,a\,$ cannot occur in $\,b\:$ so they must occur in $\,c.\,$ You should write out this argument very carefully, so that it is clear how it depends crucially on the existence and uniqueness of prime factorizations, i.e. FTA = Fundamental Theorem of Arithmetic, i.e. $\Bbb Z$ is a UFD = Unique Factorization Domain.

Besides the proof by FTA/UFD one can give more general proofs, e.g. using gcd laws (most notably distributive). Below is one, contrasted with its Bezout special case.

$$\begin{eqnarray} a\mid ac,bc\, &\Rightarrow&\, a\mid (ac,\ \ \ \ bc)\stackrel{\color{#c00}{\rm DL}} = \ (a,\ b)\ c\ = c\quad\text{by the gcd Distributive Law }\color{#c00}{\rm (DL)} \\ a\mid ac,bc\, &\Rightarrow&\, a\mid uac\!+\!vbc = (\color{#0a0}{ua\!+\!vb})c\stackrel{\rm\color{#c00}{B\,I}} = c\quad\text{by Bezout's Identity }\color{#c00}{\rm (B\,I)} \end{eqnarray}$$

since, by Bezout, $\,\exists\,u,v\in\Bbb Z\,$ such that $\,\color{#0a0}{ua+vb} = (a,b)\,\ (= 1\,$ by hypothesis). Notice that the Bezout proof is a special case of the proof using the distributive law. Essentially it replaces the gcd in the prior proof by its linear (Bezout) representation, which has the effect of trading off the distributive law for gcds with the distributive law for integers. However, this comes at a cost of loss of generality. The former proof works more generally in domains having gcds there are not necessarily of such linear (Bezout) form, e.g. $\,\Bbb Q[x,y].\,$ The first proof also works more generally in gcd domains where prime factorizations needn't exist, e.g. the ring of all algebraic integers.

See this answer for a few proofs of the fundamental gcd distributive law, and see this answer, which shows how the above gcd/Bezout proof extends analogously to ideals.

Remark  This form of Euclid's Lemma can fail if unique factorization fails, e.g. let $\,R\subset \Bbb Q[x]\,$ be those polynomials whose coefficient of $\,x\,$ is $\,0.\,$ So $\,x\not\in R.\,$ One easily checks $\,R\,$ is closed under all ring operations, so $\,R\,$ is a subring of $\,\Bbb Q[x].\,$ Here $\,(x^2)^3 = (x^3)^2\,$ is a nonunique factorization into irreducibles $\,x^2,x^3,\,$ which yields a failure of the above form of Euclid's Lemma, namely $\ (x^2,\color{#C00}{x^3}) = 1,\ \ {x^2}\mid \color{#c00}{x^3}\color{#0a0}{ x^3},\$ but $\ x^2\nmid \color{#0a0}{x^3},\,$ by $\,x^3/x^2 = x\not\in R,\,$ and $\,x^2\mid x^6\,$ by $\,x^6/x^2 = x^4\in R.\$ It should prove enlightening to examine why your argument for integers breaks down in this polynomial ring. This example shows that the proof for integers must employ some special property of integers that is not enjoyed by all domains. Here that property is unique factorization, or an equivalent, e.g. that if a prime divides a product then it divides some factor.

Using Bezout's lemma, we know that since gcd(a,b)=1, sa + tb = 1 ...(1). Multiplying both sides of this equation by c, we obtain sac + tbc = c ...(2). Now let us consider the fact that a divides bc, i.e., there exists an integer x such that ax = bc ...(3). Substituting (3) in (2) gives us sac + axc = c, taking a as common: a(sc + xc) = c; Therefore, we can say that a divides c.