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

The proof is already given in the textbook but I tried other way around.

Proof by contradiction: Let's assume that $p$ doesn't divide $a$ and $p$ doesn't divide $b$, but $p$ divides $ab$. So $\gcd(p,a)=1$ and $\gcd(p,b)=1$. Given that we can construct linear combinations

$sp+ta=1$ together with $up+wb=1$. Multiplying the left and the right sides of the equations we get

$spup+spwb+taup+tawb=1$ or $p(sup+swb+tau)+ab(tw)=1 \implies \gcd(p,ab)=1$. This is a contradiction.

Is it rigorous and sound proof?

• Seems correct to me. Feb 23, 2015 at 22:05
• Yes, one of the standard Bezout-based proofs. Feb 23, 2015 at 22:06
• Add the statement that $gcd(p,ab) = cp$ where $c \geq 1$ to make the contradiction explicit.
– John
Feb 23, 2015 at 22:07
• There is no need to make this an argument by contradiction: One easily turns your proof into one showing that if $p$ does not divide $a$ then it divides $b$: If $sp+ta=1$, then $sb(p)+t(ab)=b$, and the left-hand side is a multiple of $p$ by assumption. (You mention your book has an argument already, which I assume is this one. Your argument is correct, but I find it is better, for a variety of reasons, to avoid arguments by contradiction if possible.) Feb 23, 2015 at 22:22
• @AndresCaicedo: I tried to do that, but got downvoted since that was the proof alluded to from the book.
– robjohn
Feb 23, 2015 at 22:24

The proof is correct. Below is the same proof using gcd laws (distributive, etc), for any integer $$\,p$$.

$$\ \ \ \phantom{\frac{.}{\dfrac{.}.}} 1 = \smash[b]{\underbrace{\color{#0a0}{(p,a)}}_{\large =\, 1}\underbrace{(p,b)}_{\large =\, 1} = (\color{#0a0}{(p,a)}p,\color{#0a0}{(p,a)}b) = (p^2,ap,bp,ab) = ((\underbrace{p,a,b}_{\color{#c00}{\large =\,1}})\, p,ab) = (p,ab)}$$

where above we have used the inference: $$\ (p,a)=1\,\Rightarrow\,(p,a,b)\color{#c00}{ = 1},\,$$ and basic gcd arithmetic.

Remark  The following comparison (from here) might prove instructive ($$p$$ is any integer below)

Euclid's Lemma in Bezout form, gcd form and ideal form
\quad \smash[t]{\begin{align}\\ \\ px\!+\!ay=&\,\color{#c00}1,\,\ p\ \mid\ ab\ \ \ \Rightarrow\, p\ \mid\ b.\ \ \ {\bf Proof}\!:\,\ p\ \mid\ pb,ab\, \Rightarrow\, p\,\mid pbx\!\!+\!aby = \!(\overbrace{px\!+\!ay}^{\large\color{#c00} 1}\!) b = b\\[.2em] (p,\ \ \ a)=&\,\color{#c00}1,\,\ p\ \mid\ ab\ \ \ \Rightarrow\, p\ \mid\ b.\ \ \ {\bf Proof}\!:\,\ p\ \mid\ pb,ab\, \Rightarrow\, p\,\mid (pb,\ \ ab) = (p,\,\ \ \ a) \ b =\, b\\[.2em] P\! +\!A\ =&\,\color{#c00}1,\, P\supseteq AB\, \Rightarrow P \supseteq B.\ {\bf Proof}\!:\! P \supseteq\! PB,\!AB\!\Rightarrow\!\! P\supseteq\! PB\!+\!\!AB =(P\!+\!A)B = B \end{align}}

Note how the Distributive Law for integers is replaced by the Distributive Law for gcds and ideals in the $$2$$nd last equality in the proofs.

Generally $$\,\ c\mid ab\iff c/(c,a)\mid b\,$$ by here, or even more generally for both gcds and ideals we have $$\,(c,ab) = (c,(a,c)b).\,$$ OP is special case $$\,(c,as)=1\,$$ (for $$\,c\,$$ prime).

• +1 Another one of those disappointingly rare occasions on which someone who knows does the translation between different points of view so that the generalisation more general formulation has a clear context. Feb 23, 2015 at 23:20

Another elementary proof, which uses only euclidean division.

Let $p$ dividing $ab$, but not $a$. Consider the following set of natural numbers: $$E=\bigl\{\,n\in \mathbf N^{*}\:;\:p\mid nb\,\bigr\}.$$ $E$ is not empty since it contains $p$ and $a$. Hence it contains a smallest element, $n_0$.

Claim: $n_0$ divides all elements of $E$. Indeed, let $n$ be any element of $E$. We want to prove the remainder of the division of $n$ by $n_0$ is $0$. So let's write: $n=qn_0+r, \enspace 0\le r <n_0$.

As $p\mid nb$ and $p\mid n_0b$, $p\mid (n-qn_0)b=rb$, hence if $r\neq 0$, $r$ is an element of $E$, which contradicts $n_0$ being minimal. Thus $r=0$ and $n_0\mid n$.

In particular, $n_0\mid p$, hence $n_0=1$ or $p$. The latter case is impossible by hypothesis, since $n_0\mid a$. So $n_0=1$, and $p\mid n_0b=b$.

• Key idea $\,E\,$ is closed under subtraction, hence its least positive element divides every element. This ideal/subgroup view is emphasized in proof $(2)$ in this answer, along with $4$ other proofs of Euclid's Lemma. Here $\,E\,$ can be viewed as the denominator ideal of $\,b/p\,$ or the order ideal of $\,b\pmod p.\$ Feb 24, 2015 at 0:27
• Fine reference! Actually, the proof I ppresent can be extended to a proof of Gauß's lemma (if $n\mid ab$ and $n$ is coprime with $a$, then $n\mid b$. Feb 24, 2015 at 0:52
• Yes, that's true for most proofs of Euclid's Lemma. Feb 24, 2015 at 0:53
• See also both of my answers here for some conceptual ways to perform such descent-based proofs. Nov 2, 2016 at 3:32
• @jiten: $1$. No, $n$ is a generic name for any natural number such that $p$ divides the product $nb$. In particular, $a$ is one of these numbers, by hypothesis,and $p$ is another, because $p$ obviously divides $pb$. $2$. Where did you find that $p\mid b$? That's what we have to prove if we suppose $p$ doesn't divide $a$. $3$.~Yes, but why do you want to rename $n_0$ $a_0$? Jun 15, 2018 at 22:22

I hope that it is also another elementary proof 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$".

NB : It will just work in Euclidean Domains like $\mathbb{Z}$.

• There is no notion of size or a norm in a PID so this proof is not valid for that case. You use the fact that $0 < |r_1| < p$ which is only applicable in Euclidean Domains (which are a subset of PID), since you can say $N(r_1) < N(p)$. Jan 12, 2017 at 19:12
• @gowrath indeed thank you for confirmation ! Nice in $\mathbb{Z}$ !!! Jan 12, 2017 at 20:46