# Proof of Euclid's Lemma

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.

• I believe they meant to write $0<i<p$. But the proof seems awfully sketchy to me. Not entirely clear how we are meant to see the claim for $ci$. It's true, of course, but is it really easier than the orignal problem? Usual argument goes via Bezout's Identity en.wikipedia.org/wiki/B%C3%A9zout%27s_identity – lulu Dec 18 '15 at 15:46
• Yes, I am trying to find an argument that does not use Bezout's Identity. – Martin Copes Dec 18 '15 at 15:47
• There aare elementary proofs, that use only euclidean division and $\mathbf N$ being well-ordered. – Bernard Dec 18 '15 at 15:48
• @Bernard I would love to see one of those proofs! – Martin Copes Dec 18 '15 at 15:49
• Well, I wrote one a couple of months ago (I think the ideas are Cauchy's),. See my answer to this question. – Bernard Dec 18 '15 at 15:55

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.

• This is a neat answer! I wonder why it has not been rated yet. This even works in bounded arithmetic. – dragoon Oct 18 '18 at 9:56

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

• I am trying to find a proof that does not use GCD. That is why I stumbled upon that proof. Any idea of a proof of this lemma that does not use GCD? – Martin Copes Dec 18 '15 at 15:50
• @MartinCopes Oh, you should probably add that to the question then. I don't know a proof directly. But the euclidian algorithm is pretty elementary, so why avoid it? – Jorik Dec 18 '15 at 15:52
• This proof basically uses Bezout's Identity. – Arnav Poddar Oct 13 '19 at 17:24

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.

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!

• Unfortunately I am trying to use Euclids Lemma to prove the FTA so I can not use it! I was looking for a way to fix the proof I wrote. – Martin Copes Dec 18 '15 at 16:30
• I think the step in your modular arithmetic proof where you factor out $b\equiv a$ tacitly assumes the very result you're trying to prove. – Barry Cipra Dec 18 '15 at 17:34
• @BarryCipra yeah you're probably right. Your contradiction is the most elegant answer, well done. – Colm Bhandal Dec 18 '15 at 17:45
• @ColmBhandal, thank you. I like the warning you added! – Barry Cipra Dec 18 '15 at 17:58

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

• I understand that if i < p then p is not a factor or i, but why must it then be a factor of c? It is what I am trying to prove!! It gets circular, right? – Martin Copes Dec 18 '15 at 16:24

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.

• How can you prove that 1 = s p + t b? I need a proof that does not use the gcd algorithm. – Martin Copes Dec 18 '15 at 20:38
• @MartinCopes why do you need a proof that does not use that? Do you mean you need a self-contained proof? – Leandro Caniglia Dec 18 '15 at 20:39
• Indeed. I am writing the proof in Coq and it is for educational purposes so I don't want to overcomplicate things coding the gcd function and proving it correct and that stuff... – Martin Copes Dec 18 '15 at 20:41