# If a prime $p\mid ab$, then $p\mid a$ or $p\mid b\$ [Euclid's Lemma]

If a prime number $p$ is a divisor of a product $ab$, $p$ has to be a divisor of $b$ or $a$. How can I demonstrate this theorem? I demonstrated this theorem on one way using Bezout's theorem in an answer below but are there other proofs??

• What is your definition of prime number? – Aaron Maroja Apr 1 '15 at 19:54
• A number $p$ is a prime number if $p$ is divisibile for 1 and $p$ – Domenico Vuono Apr 1 '15 at 19:59
• What Aaron means is that in some contexts, what you want to prove is just the definition of being prime. However if you use your definition (which as Aaron also notes, is what's usually called irreducible), what you ask does need to be proved. – GPerez Apr 1 '15 at 20:18
• @JyrkiLahtonen these are not really dupes in my opinion. Especially the one into which users now vote into is not the same question. (I'd assume there are dupes; but these are not.) – quid Apr 1 '15 at 20:42
• I guess you're right, @quid. At least I had the sense not to close it. I still think it very likely that this is a dupe of ... something that it is too late an hour for me to search for. – Jyrki Lahtonen Apr 1 '15 at 20:49

The set $$\,S\,$$ of naturals $$\,n\,$$ such that $$\,\color{#c00}{p\mid nb}\,$$ is $$\rm\overbrace{closed\ under\ subtraction}^{\overbrace{\large p\mid nb,kb\,\Rightarrow\, p\mid nb-kb\, =\, (n-k)b}^{\LARGE n,\,k\ \in\ S\ \ \ \Longrightarrow\ \ \ n-k\ \in\ S\ \ }}$$ and $$\, a,p\in S\,$$ therefore by the Lemma its least positive element $$\,\color{#0a0}{d\mid a,p}.\,$$ Since $$\,\color{#a0f}{d\mid p\ \ \rm prime},\,$$ either $$\,\color{#a0f}{d=p}\,$$ (so $$\ \color{#a0f}{p = }\color{#0a0}{d\mid a}),\,$$ or $$\,\color{#a0f}{d=1}\in S\$$ (so $$\ \color{#c00}{p\mid d b = b}),\$$ i.e. $$\,\ p\mid \color{}a\,$$ or $$\ p\mid \color{}b.\ \$$ QED

Lemma $$\ \$$ Let $$\,\rm S\ne\emptyset \,$$ be a set of integers $$>0$$ closed under subtraction $$> 0,\,$$ i.e. for all $$\rm\,n,m\in S, \,$$ $$\rm\ n > m\ \Rightarrow\ n-m\, \in\, S.\,$$ Then the least $$\rm\:\ell\in S\,$$ divides every element of $$\,\rm S.$$

Proof $${\bf\ 1}\,\$$ If not there is a least nonmultiple $$\rm\,n\in S,\,$$ contra $$\rm\,n-\ell \in S\,$$ is a nonmultiple of $$\rm\,\ell.$$

Proof $${\bf\ 2}\,\rm\,\ \ S\,$$ closed under subtraction $$\rm\,\Rightarrow\,S\,$$ closed under remainder (mod), when it is $$\ne 0,$$ since mod is simply repeated subtraction, i.e. $$\rm\ a\ mod\ b\, =\, a - k b\, =\, a\!-\!b\!-\!b\!-\cdots\! -\!b.\,$$ Thus $$\rm\,n\in S\,$$ $$\Rightarrow$$ $$\rm\, (n\ mod\ \ell) = 0,\,$$ else it is in $$\,\rm S\,$$ and smaller than $$\rm\,\ell,\,$$ contra minimality of $$\rm\,\ell.$$

Remark $$\$$ In a nutshell, two applications of induction yield the following inferences

$$\begin{eqnarray}\rm S\ closed\ under\ {\bf subtraction} &\Rightarrow\:&\rm S\ closed\ under\ {\bf mod} = remainder = repeated\ subtraction \\ &\Rightarrow\:&\rm S\ closed\ under\ {\bf gcd} = repeated\ mod\ (Euclid's\ algorithm) \end{eqnarray}$$

Interpreted constructively, this yields the extended Euclidean algorithm for the gcd.

If fractions are known then $$\,S\,$$ can be interpreted as the set of all possible denominators of $$\,b/p,\,$$ since $$\,ap = nb \iff a/n = b/p.\,$$ See various posts on denominators ideals for more.

The Lemma describes a fundamental property of integer arithmetic whose essence will become clearer when one studies ideals of rings, viz. a Euclidean domain is a PID, i.e. in any domain $$D$$ enjoying a Euclidean algorithm for division with remainder, all ideals $$I$$ are principal, i.e. $$\, I = dD\,$$ where $$d$$ is the least nonzero element of the ideal (= gcd of all elements). Here a subset $$\,I\subset D$$ is an ideal if is closed under subtraction and scaling by elements of $$D$$. The proof is exactly as in the 2nd proof above - by Euclidean descent using remainder (mod) via the division algorithm, e.g. see here and here and here.

See here for a few alternative proofs.

See here for a precise comparison of various forms of Euclid's Lemma

Variations of the above Theorem yield analogous "direct proofs" of the Fundamental Theorem of Arithmetic (existence and uniqueness of prime factorizations of integers), e.g. see this answer. Various forms of such direct proofs were given by Klappauf, Lindemann, and Zermelo.

• I was sure to see you here. Nice answer. – quid Apr 1 '15 at 21:08

Here is one, which uses only euclidean division and the well-order on $\mathbf N$:

Let $E = \bigl\{x ∈ \mathbf N^{\boldsymbol *} \mid p\enspace \text{divides}\enspace xb\}$ . $E$ is not empty, since it contains at least $p\,$ and $\,a$.Thus it contains a smallest element, $x_0$.

This element divides each $x\in E$: indeed the euclidean division of $x$ by $x_0$ gives: $\,x = qx_0 + r\enspace(0 ≤ r < x_0)$. As $x, x_0$ are in $E$, $p$ divides $xb$ and $x_0b$, hence $(x-qx_0)b =rb$. Thus, if $r\neq 0$, $r\in E$. This is impossible since $x_0$ is the smallest element in $E$. So $r = 0$ i.e. $\,x_0$ divides $x$.

In particular, $x_0$ divides $p$ et $a$, which belong to $E$ ; as $p$ and $a$ are coprime, $x_0 = 1$. Thus, $p$ divides $x_0 b = b$.

• When you say only... :p – GPerez Apr 1 '15 at 20:15
• @GPerez: Well? Isn't it true it uses only elementary results? – Bernard Apr 1 '15 at 20:24
• Now I'm not sure if you're joking (mainly because I'm still learning these things), but isn't Euclidean strictly stronger than having a Bézout identity? I will say that well-order escapes me as far as how necessary it is for general discussion of rings, seeing as my professors never mentioned it, rather they probably applied it directly. – GPerez Apr 1 '15 at 20:44
• You can say it's stronger, but there remains euclidean division of natural numbers is more elementary, since it's taught in elementary school. Moreover, to derive Bézout's identity, you have to prove $\mathbf Z$ is a PID, which relies … on euclidean division. As for well-ordering it's just a way to assert what everyone knows: any set of natural numbers has a smallest element. So, yes, the proof I gave is elementary, and it gives an idea of the beauty of mathematics (I can say it since, of course, I didn't find this proof). – Bernard Apr 1 '15 at 21:23
• @GPerez All proofs essentially use the Euclidean algorithm, even if they disguise it. For example, in my answer I completely unwind the Euclidean algorithm into (repeated) subtraction (which facilitates an elementary view of the ideal-theoretic essence of the matter). – Bill Dubuque Apr 1 '15 at 21:49

If $p\not\mid a$, then $\gcd (p,a)=1$ (why?). Since $p\mid ab$ and $\gcd (p,a)=1$, the Euclid's lemma implies that $p\mid b$.

• This is one of the cleanest ways to get to the solution. :) – user75930 Apr 1 '15 at 20:50
• @Sabyasachi This is essentially the same as the solution already posted by the OP. – Bill Dubuque Apr 1 '15 at 21:41
• @Fermat It's precisely equivalent unless you prove Euclid's Lemma by some way other than Bezout. Invoking a Lemma by name (vs, proving it inline) doesn't alter proof equivalence. – Bill Dubuque Apr 1 '15 at 21:55
• Update: I posted a non-Bezout proof here of this form of Euclid's Lemma (actually slightly more general). That is one way to do what you seek. – Bill Dubuque Apr 2 '15 at 15:48
• @Fermat That would likely be a circular proof, since most proofs of uniqueness of prime factorizations employ Euclid's Lemma. To avoid such circularity you would need to give a direct proof of uniqueness, e.g. using one of the direct proofs in answers here (e.g. see the Zermelo-like proof that I link to). By the way, it was not I who downvoted.. – Bill Dubuque Apr 2 '15 at 17:55

I demonstrated this little theorem through the Bézout's theorem: If a prime number $p$ isn't a divisor of $a$, $(a,p)=1$ because the only divisors of $p$ are $p$ and $1$. Then there are two numbers $k$ and $l$ such that: $1=ka+lp$. Multiplying this equality by $b$ we obtain : $b=kab+lpb$ but if $p$ is a divisor of $ab$: $ab=pr$ for some $r\in \mathbb{Z}$ and $b=kpr+lpb=p(kr+lb)$. From this relationship we can note that $p$ is a divisor of $b$. Are there other demonstrations?? Help me!

• No.. I prove that p doesn't divide $a$, $p$ has to divide $b$ – Domenico Vuono Apr 1 '15 at 19:28
• My mistake, your proof is correct. – GPerez Apr 1 '15 at 19:32
• Your proof is correct and I think this is the simplest! – Extremal Apr 1 '15 at 19:38
• You have essentially repeated the Bezout-based proof of Euclid's lemma, i.e. the Lemma that $\,(c,a)=1,\ c\mid ab \,\Rightarrow\, c\mid b\,$ in the special case prime $\,c = p\nmid a.\$ Better to invoke the lemma by name rather than repeat its proof in this special case. – Bill Dubuque Jun 21 '16 at 21:00

Edit: Read the comments, this can't be used to prove what OP asks, in the way he asks it (but it can be used to prove that irreducible $\Leftrightarrow$ prime in UFDs)

Another proof could be as follows. You know that $a$ and $b$ factorize uniquely (save multiples by $\pm 1$) as $$a = p_1\cdots p_r \\ b = p'_1\cdots p'_s$$ By the divisibility hypothesis, say that $px = ab$, and again factorize $x$: $$x = p''_1\cdots p''_t$$

Then you have, by expanding $px = ab$ $$pp''_1\cdots p''_t = p_1\cdots p_rp'_1\cdots p'_s$$ This is an equality between prime factorizations, so it must be that each of the prime factors on the right hand side divide a certain prime on the left hand side. In particular, $p$ divides either a certain $p_i$, or a certain $p'_j$. This concludes the proof.

This isn't on first glance an improvement to your own proof. Indeed it seems more complicated. However it is advantageous to know this proof, as it doesn't rely on the existence of the Bézout identity, and can be directly transported to more general contexts.

• I think this prof is correct – Domenico Vuono Apr 1 '15 at 19:46
• It depends how one proves FTA. Ususally FTA is proven using Euclid's lemma (i.e. the fact this question is about) so one has to be careful here for circular reasonings. – Bart Michels Apr 1 '15 at 19:59
• @barto Well noted. I checked my notes on rings though and it seems that uniqueness of prime factorizations can be proved without the lemma (and so can existence in $\Bbb Z$). – GPerez Apr 1 '15 at 20:12
• In that context however a prime element is usually defined via the property to be proved in OP. It is however also true that a Bézout type identity is not strictly necessary to show existence and uniqueness of a factorization into prime elements as there are UFDs that do not have such a Bézout like identity. Still I would recommend to double check what is actually proved for the integers in your notes. – quid Apr 1 '15 at 20:31
• @quid I was typing this as your comment came up... I double checked and my notes in fact use the definition of primes as you say. I guess that Euclid's Lemma is then equivalent to FTA! (making my proof unsalvageable) – GPerez Apr 1 '15 at 20:38

Here's a fun little proof by contradiction. The only facts about primes that is uses is that all primes are greater than $1$, every number greater than $1$ has a prime divisor, and no prime divides any other prime.

Suppose there were a counterexample. Then there would be one with a least prime number $p$. For that prime, there would be one with a least (positive) value for $a$. Clearly $a$ cannot equal either $1$ or $p$. Nor can it be greater than $p$, since $a-p$ would then provide a smaller counterexample. So there would be a counterexample with $1\lt a\lt p$.

Now let $q$ be a prime divisor of $a$. There must be such a prime $q$ since $a\gt1$, and $q$ must be less than $p$ since $a\lt p$. But when we write $ab=pk$, we find that $q\mid pk$ and $q\not\mid p$, so the minimality of $p$ implies $q\mid k$. Letting $a=qc$ and $k=qh$, we find $cb=ph$, with $c\lt a$ (since $q\gt1$), and this contradicts the minimality of $a$.

• This is one of the variants I mention in my answer, due to Klappauf or Lindemann if memory serves correct. The disadvantage of this method is that it is a bit harder to see the relationship with more conceptual (or constructive) methods (via ideals or the Euclidean algorithm). – Bill Dubuque Apr 2 '15 at 17:29

This can be proved directly (using no lemmas, only subtraction and induction) as follows.

If prime $$\ p\mid ab,\ p\nmid a\,$$ then $$\,p,a\ {\rm are\ coprime\, \ and}\ \ p\mid pb,ab\ \color{#c00}\Rightarrow\ p\mid b,\,\$$ by

Theorem $$\,\$$ If $$\ \bar a,a,b,c\,$$ are positive integers then

$$\quad\qquad\qquad\qquad\qquad\quad\ \ \bar a,a\ {\rm are\ coprime\ \ and}\ \ c\mid \bar ab,ab\ \color{#c00}\Rightarrow\ c\mid b$$

Proof $$\$$ Induct on $$\,\color{#90f}{{\rm size}:= \bar a+a}.\,$$ It is true if $$\,\bar a=a\!:\,$$ $$\, \bar a,a\,$$ coprime $$\,\Rightarrow\, a=1\,$$ $$\,\Rightarrow\,c\mid ab = b.\,$$ Else $$\,\bar a\neq a\,$$ so wlog, by symmetry, $$\,\bar a > a\,$$ so $$\,\color{#0a0}{c\mid (\bar a\!-\!a)b,ab}\,$$ and $$\,\bar a\!-\!a,a\,$$ are coprime. By the smaller $$\rm\color{#90f}{size}$$ $$\,(\bar a\!-\!a) + a = \bar a < \color{#90f}{\bar a+a}\,$$ of the $$\,\rm\color{#0a0}{above\ instance},\,$$ induction yields $$\,\color{#0a0}{c\mid b}\ \$$ QED

Remark $$\,\ \bar a,\,a\,$$ coprime $$\,\Rightarrow\,\bar a\!-\!a,a\,$$ coprime, since $$\ d\mid \bar a\!-\!a,\,a \,\Rightarrow\,d\mid \bar a=(\bar a\!-\!a)+a,\,$$ hence $$\,\ d\mid \bar a,a\,$$ $$\Rightarrow$$ $$\ d=1.\,$$ If properties of gcds are known then the proof is easer, namely

$$c\mid \bar ab,ab\,\Rightarrow\, c\mid \gcd(\bar ab,ab) = \gcd(\bar a,a)b = b$$ The first proof is essentially the same as this, except that the gcd structure has been eliminated, unwound into its primitive constituents of repeated subtraction and induction. This proof is a gcd analog of the common Bezout-based proof posted in your answer.

Corollary (Euclid's Lemma) $$\ \ c,a\,$$ coprime, $$\,c\mid ab\,\Rightarrow\, c\mid b,\$$ by $$\ \bar a := c\,$$ in the Theorem.

See here for a precise comparison of various forms of Euclid's Lemma

Variations of the above Theorem yield analogous "direct proofs" of the Fundamental Theorem of Arithmetic (existence and uniqueness of prime factorizations of integers), e.g. see this answer. Various forms of such direct proofs were given by Klappauf, Lindemann, and Zermelo.

I hope it is also an elementary proof (probably the ugliest) of this lemma :

Let's assume that $p$ (a prime number) doesn't divide $a$ and $p$ doesn't divide $b$.

That means that $\exists\ (k_1,r_1), (k_2,r_2) \in \mathbb{Z}\times\mathbb{Z}^*$ such as :

$a=pk_1+r_1$ with $0<\vert r_1\vert <p$ and $b=pk_2+r_2$ With $0<\vert r_2\vert <p$

$\Rightarrow$ $ab=(pk_1+r_1)(pk_2+r_2)=p(pk_1 k_2 + k_1 r_2 + k_2 r_1)+r_1 r_2 = pK+R$

$p$ doesn't divide $R$. Indeed if $p$ divided $R=r_1 r_2$ with $\gcd(p,r_1)=1$ by Gauss Lemma $p$ should divide $r_2$. Impossible.

Hence, $p$ doesn't divide $ab$.

I conclude by contraposition that : if $p$ doesn't divide $a$ and $p$ doesn't divide $b$ then $p$ doesn't divide $ab$.

With this method, I can easily generalize this lemma to $n$ numbers : "If $p$ is a prime number which divides $a_1 a_2 ... a_n$ then $p$ divides $a_1$ or ... or $a_n$".

PS : I don't know if it works in PID, can anyone confirm ?

• The reduction mod $p$ is not needed. If you're going to use said Gauss / Euclid Lemma then note $\ p\nmid a\,\Rightarrow\, (p,a) = 1\,$ so $\,p\mid ab\,\Rightarrow\, p\mid b\,$ by the Lemma. But the OP already posted an answer using a Bezout-based proof of the Lemma, and seeks alternatives, e.g. by gcd laws as below $$p\mid ab\iff \,p\mid ab,pb\iff p\mid (ab,pb) = (a,p)b = b$$ This is more general then the Bezout-based proof since it works in any gcd-domain, e.g. $\,\Bbb Q[x,y],\,$ where e.g. $\,\gcd(x,y) = 1 \neq x f + y g\$ – Bill Dubuque Jun 21 '16 at 20:53
• @BillDubuque Ok the reduction was here to detail the method – Maman Jun 22 '16 at 19:58
• My point is that you don't need both $\,a,b\,$ to be less than $p$ to apply the Gauss / Euclid Lemma. Instead you can use the short proof I gave in my prior comment. – Bill Dubuque Jun 22 '16 at 20:18

Lemma 1: If $$p$$ is a prime number, $$a \ge 2$$ and $$p \nmid a$$ then we can specify
an integer $$\gamma(p,a)$$ (see the proof details for the exact mapping) satisfying

$$\tag 1 p \nmid \gamma \quad \land \quad 1 \le \gamma\lt a$$ Proof
Case 1: $$a \ge p$$
Set $$\gamma = a - p$$. Using the laws/properties of inequalities and the hypothesis we conclude that the right conjunctive of $$\text{(1)}$$ is true; the left conjunctive is easily seen to be true.

Case 2: $$a \lt p$$
Using Euclidean division,

$$\tag 2 p = aq + r \quad \text{where } 0 \le r \lt a$$

Set $$\gamma = r = p -aq$$. Using the lemma's hypothesis we must have $$\gamma \ge 1$$ and so conclude that the right conjunctive of $$\text{(1)}$$ is true. Using the transitive law of inequality we get $$\gamma \lt p$$ and since $$p$$ can't divide a smaller positive integer, the left conjunctive of $$\text{(1)}$$ is true. $$\quad \blacksquare$$

Proving the following two lemmas (over the integers) is an easy assignment;
note that they constitute the '$$\gamma$$ aware' logic that is implicitly used in the final proposition.

Lemma 2: If $$p \mid ab$$ then $$p \mid (a-p)b$$.

Lemma 3: If $$p \mid ab$$ then $$p \mid (p-aq)b$$.

Proposition 4: Let integers $$a, b, p \ge 1$$ with $$p$$ a prime number. If $$p\mid ab$$, then $$p\mid a$$ or $$p\mid b$$.
Proof
If $$p \mid a$$ the proposition is true so we assume that we can write as true

$$\tag 3 p\mid ab \quad \land \quad p\nmid a$$

and need an argument showing that $$p\mid b$$.

If $$a = 1$$ then by $$\text{(3)}$$ we have $$p \mid 1 \times b$$ and the proposition is true.

Assuming $$a \ge 2$$, the above lemmas and the absurdity of infinite descent allows us to recursively construct (keep applying $$\gamma$$) a sequence with $$k \gt 0$$ steps

$$\tag 4 a_0( = a) \gt a_1 \gt \dots \gt a_k (= 1)$$

satisfying

$$\tag 5 p\mid a_j b \quad \land \quad p\nmid a_j \quad \text{ for } 0 \le j \le k$$

But then $$p \mid b$$. $$\quad \blacksquare$$

$ab$ contains p as it's prime factor. That's what $p|ab$ means. Since $p$ is prime, it can't be expressed as product of two numbers except $1$ and $p$. So either $a$ should contain it or $b$.