# 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\not\mid b$$ AND $$a\mid bc$$. This implies that $$a$$ divides $$c$$. 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 Commented Jun 11, 2013 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. Commented Jun 11, 2013 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 Commented Jun 11, 2013 at 15:03
• Ok, notice in your reasoning applies to any numbers $a,b,c$ such that $a$ does not divide $b$ and $a$ does divide $bc$. However people have provided counterexamples to $a$ dividing $c$ from these hypotheses. Yet if your proof was correct it would work for these too! Hence your proof is incorrect. Commented Jun 11, 2013 at 15:34
• 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). Commented Jun 11, 2013 at 16:00

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

• you just repeated what someone already said, i want to know why my way of doing this problem is wrong. Commented Jun 11, 2013 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
Commented Jun 11, 2013 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. Commented Jun 11, 2013 at 14:35
• If somebody wants to know the importance of being the two numbers relatively prime so how we convince him?
– user63181
Commented Jun 11, 2013 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? Commented Jun 11, 2013 at 14:21
• YOu are assuming the result you wish to conclude as "obvious." It is not and I supply the reason it works. Commented Jun 11, 2013 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 Commented Jun 11, 2013 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? Commented Jun 11, 2013 at 14:32
• @mathworld Since $a\nmid b$, $b=aq+r$ for some $r<a$. Suppose $c=aq' + s$. Then $bc=a^2qq' + aqs + aq'r + rs$. From this we get that $a$ divides $rs$. How can you conclude that $s=0$? Commented Jun 11, 2013 at 15:40

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. This and related methods of proof are presented in this answer.

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

• Did you mean that are not where you typed there are not? Commented Sep 22, 2023 at 16:53

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

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.

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 you conclude that $$a|c$$. This part is wrong. It is possible to have $$a$$ does not divide $$b$$ AND $$a$$ divides $$bc$$, but $$a$$ does not 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 Commented Jun 11, 2013 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$? Commented Jun 11, 2013 at 15:43
• you ignore the fact that i said you start with two numbers relatively prime Commented Jun 11, 2013 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.... Commented Jun 11, 2013 at 16:16

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. Commented Jun 11, 2013 at 14:30

The proof of the proposition in question has already been proved brilliantly, but I would like to add one more detail. The method you mentioned is incorrect for one very important reason:

## $$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\\\\\\\\\\ \ \ \ \ \ \ \ \$$$$a$$ is not necessarily prime!

This implies that $$a$$ divides $$c$$.

This implication is only valid if a is prime. Hence, considering $$a$$ is a prime number, if $$a|bc$$, then $$a|b$$ OR $$a|c$$. We also know that $$gcd(a,b)=1$$ which means that $$a|c$$.