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

Question

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??

Answer 1

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.

Answer 2

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!

Answer 3

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)

Original Answer:

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.

Answer 4

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

Answer 5

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

Answer 6

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 easier, 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.

Answer 7

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

Answer 8

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 ?