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.

Solution 1:

By Bézout's theorem and since $\gcd(a,b)=1$ then 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$.

Solution 2:

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.

Solution 3:

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

Solution 4:

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

Solution 5:

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