Proof of Euclid's Lemma

Question

I saw on the internet the following Proof of Euclid's lemma, which states that if a prime number divides the product of two numbers, then it must divide at least one of the two numbers.

Since $p \mid bc$, there exists an integer $n$ such that $bc = np$. Now, assume $p\nmid b$. I.e. there are integers $k, i$ with $0< i < p$, such that $b = kp + i$

And therefore, $$np = bc = c(kp +i ) = kpc + ci \implies ci = p(n - kc)$$ So, $p$ is a factor of $ci$ and since $0 < i < k$ , $p$ must be a factor of $c$.

I am particularly confused by the last statement:

... since $0 < i < k$, $p$ must be a factor of $c$

This does not make sense to me... $i$ needs not be less than $k$.

This proof was selected as the best answer in a Yahoo question

I would be grateful if someone could explain me what is going on at the end of the proof or if it is wrong.

UPDATE: I need a proof that does not use the gcd algorithm.

Answer 1

I think that it was meant that $0<i<p$. However this doesn't actually help. The proof is a bit of a circular argument since we still have that $p$ divides a product and want to conclude it divides one of the factors.

The easiest way to proof Euclid's lemma involves the extended euclidean algorithm. If $p\nmid b$ then $\gcd(p,b) = 1$. So using the extended euclidean algorithm we can find $r$ and $s$ so that $rp+sb=1$. Now we multiply by $c$ to get $$rpc +sbc = c$$ Cleary $p\mid rpc$ but also $p\mid sbc$ since it was given that $p\mid bc$. So $p$ must also divide their sum, which is $c$.

Answer 2

Answer Using Modular Arithmetic

Warning: Modular arithmetic may be "using a bazooka to shoot itself" i.e. it's not only using too much machinery, but the argument may be circular. For these kind of results, it's best to go to first principles, so I recommend Barry Cipra's answer. It is quite slick.

OK, it has been stated that we can't use FTA to prove this. So we really need to go under the hood. Not to worry, residues to the rescue. Since $c$ is a natural number, we can case analyse it as being $1$ or some number plus $1$. Clearly the case for $c=1$ is true, for this implies $p \mid b$, immediately giving us one of our disjuncts.

Moving on to the $c+1$ case, suppose $p \mid b(c + 1) = bc + b$. Now, either $p \mid b$, and we're done, or else $b \equiv a \;\; (\text{mod}\: p)$, with $0 < a < p$. Then $bc \equiv -a \;\; (\text{mod}\: p)$ because we already know that $bc + b \equiv 0 \;\; (\text{mod}\: p)$. But then we can factor out the $b \equiv a$ to get $c \equiv -1 \;\; (\text{mod}\: p)$. And so $c + 1\equiv 0 \;\; (\text{mod}\: p)$, as required.

Old Answer Using FTA

I agree with Jorik in that the proof is somewhat circular, and I admire his elegant answer. However, if you are looking for a proof from first principles, I believe this should be proved with the most fundamental theorem in number theory: the fundamental theorem of arithmetic. It gives us that every number can be decomposed into a unique product of primes. So we proceed as follows:

Decompose $b$ and $c$ into a product of primes as follows:

• $b = p_1^{k_1} p_2^{k_2} \dots p_n^{k_n}$
• $c = q_1^{j_1} q_2^{j_2} \dots q_m^{j_m}$

Then we have that

$$bc = p_1^{k_1} p_2^{k_2} \dots p_n^{k_n}\cdot q_1^{j_1} q_2^{j_2} \dots q_m^{j_m} \dots (1)$$

Now we have that $p \mid bc$ which means that $bc = pn$ for some $n$. Again, apply the fundamental theorem to $n$, writing $n = r_1^{i_1} r_2^{i_2} \dots r_x^{k_x} $ and combine $bc = pn$ with $(1)$ and we get:

$$p_1^{k_1} p_2^{k_2} \dots p_n^{k_n}\cdot q_1^{j_1} q_2^{j_2} \dots q_m^{j_m} = bc = pn = p \cdot r_1^{i_1} r_2^{i_2} \dots r_x^{k_x} \dots (2)$$

Now we use the second fact of the fundamental theorem: uniqueness up to reordering. This combined with $(2)$ gives us that $p$ must appear somewhere in the product

$$p_1^{k_1} p_2^{k_2} \dots p_n^{k_n}\cdot q_1^{j_1} q_2^{j_2} \dots q_m^{j_m}$$

So there is some $i$ such that $p=p_i$ or $p=q_i$. So $p$ divides either $b$ or $c$ respectively.

Aside: Stick with Stack Exchange, we're way better than Yahoo answers!

Answer 3

Suppose there were a counterexample, with $pa=bc$, $p$ a prime, but neither $b$ nor $c$ divisible by $p$. Then there would be a counterexample with $p$ as small as possible and, for that $p$, $b$ as small as possible. Note that $b\gt1$, since otherwise we would have $pa=c$, which means $p$ divides $c$.

We first note that $b\lt p$, since otherwise $pa'=p(a-c)=(b-p)c=b'c$ would be a smaller counterexample. But now $b\gt1$ implies $b$ is divisible by some prime $q$, which means we have $q$ dividing $pa$ with $q\le b\lt p$. By the minimality of $p$ as a counterexample, we conclude that $q$ divides $a$ (since it can't divide $p$). If we now write $a=a'q$ and $b=b'q$ and note that $b'\lt b\lt p$ implies $p$ doesn't divide $b'$ either, we find that $pa'=b'c$ is a smaller counterexample, which is a contradiction. Thus there can be no counterexample.

Remark (added later): The subtlety of Euclid's lemma is sometimes demonstrated with examples of multiplicative systems in which the lemma does not hold. One standard example is the set of positive integers congruent to $1$ mod $4$; another is the set of even integers. For the set $\{1,5,9,13,17,21,\ldots\}$ we have $9$, $21$ and $49$ as primes -- that is, none is the product of other numbers in the set (except, of course, themselves times $1$) -- yet $9\cdot49=21\cdot21$. As for the even integers, the primes are $\{2,6,10,14,18,\ldots\}$ -- that is, anything that's twice an ordinary odd number -- yet $2\cdot30=6\cdot10$.

It's worth seeing where the proof given above fails for these examples.

The failure point in both cases is in the statement "otherwise $pa'=p(a-c)=(b-p)c=b'c$ would be a smaller counterexample," but for different reasons. The set of integers congruent to $1$ mod $4$ is not closed under subtraction, so the statement simply makes no sense. For the set of even integers, the statement makes sense, but it's not true: $2$ does not divide $6$, but it does divide $6-2=4=2\cdot2$. What's going on is that, although the even integers are a ring, it's a ring without a unit (because $1$ is odd, not even): The theorem $d\mid n\implies d\mid (n+d)$ holds because its proof goes $d\mid n\implies n=dm\implies n+d=dm+d=d(m+1)\implies d\mid (n+d)$, and that proof falls apart if you don't have the number $1$.

Alternative proof (added later): I wondered from the outset if it was really necessary to make the double assumption that both $p$ and $b$ (given $p$) are as small as possible. It turns out it's enough to assume you have a counterexample with minimal $b$.

Among all counterexamples $pa=bc$ (with $p$ prime and not dividing either $b$ or $c$), there would have to be one with minimal $b$. Note that $b\not\mid a$, since otherwise $p$ would divide $p(a/b)=c$. Note also that $b\not\mid p$.

We first argue that $b$ must itself be prime. If not -- if $b=b'b''$ with $b',b''\lt b$ -- then either $p\mid b'(b''c)$ or $p\mid b''c$ would be a smaller counterexample. That is, since $p$ doesn't divide $b$, it can't divide any divisor of $b$ (that's true whether $p$ is prime or not), so if the minimality of $b$ rules out $b'(b''c)$ as a counterexample (because $b'\lt b$), we must conclude $p$ divides $b''c$, which itself violates the assumed minimality of $b$.

Now write $p=bk+r$ with $0\lt r\lt b$. (We have $0\lt r$ since $b\not\mid p$.) Since $b$ divides $pa$, it also divides $ra$, but $b$ clearly doesn't divide $r$ (since $0\lt r\lt b$) nor, as noted above, does it divide $a$. So this gives us a new counterexample: a prime number, $b$, that divides a product, $ra$, without dividing either factor. Most important, the first of those factors, $r$, is smaller than $b$. This contradicts the assumed minimality of $b$, so we can conclude that no counterexamples exist.

Answer 4

I believe it's a typo, and should read "since i < p, p must be a factor of c, since p cannot be a factor of a number smaller than it."

Answer 5

The proof is wrong. In fact under the hypothesis that p divides bc one can always assume that both b and c are smaller than p (otherwise, just replace them with their remainders mod p, which is essentially what this "proof" does). In this "simpler" case (b, c < p) the constant k in the "proof" is 0and the division did nothing (i = b).

In order to prove the theorem you have to prove first another theorem that states that if p is irreductible (meaning it cannot be expressed as a product of two proper factors) and p does not divide b, then there exist two integers s and t such that:

1 = s p + t b

The reason behind this theorem (which I'm not proving here) is that always the gcd(a,b) can be expressed as a linear integer combination of a and b (the proof proceeds by generating a sequence of divisions until you get the gcd).

Now, for the proof you are looking for, just multiply the equation above by c and get

c = scp + tbc = (sc + tn)p

and p divides c.