= Euclid's lemma
{c}
{title2=$p\mid ab\Longrightarrow p\mid a\text{ or }p\mid b$}
{wiki}
= Euclid lemma
{c}
{synonym}
If a <prime number> $p$ divides a <product> $ab$ of <integers> $a,b$, then $p$ divides $a$ or $b$ (possibly both):
$$
p\mid ab\quad\Longrightarrow\quad p\mid a\text{ or }p\mid b.
$$
For example, $5\mid6\cdot10$ and $5\mid10$. The hypothesis that $p$ is a <prime number> matters: $6\mid2\cdot3$, although six divides neither factor. When $p$ does not divide $a$, the <greatest common divisor> of $p$ and $a$ is one; multiply <Bézout's identity> $up+va=1$ by $b$ to see that $p\mid b$. Repeated application makes this the uniqueness step in the <fundamental theorem of arithmetic>. https://mathcs.clarku.edu/~djoyce/elements/bookVII/propVII30.html[Euclid, Elements, Book VII, Proposition 30]{ref}.
For a completely computed example, $7\mid20\cdot21$ because $20\cdot21=420=7\cdot60$, while $20=7\cdot2+6$ shows that seven does not divide twenty. <Bézout's identity> $3\cdot7-20=1$ becomes, after <multiplication> by $21$,
$$
21=3\cdot7\cdot21-20\cdot21=7\cdot63-7\cdot60=7\cdot3.
$$
The two terms on the right are divisible by seven, which explicitly recovers the forced <divisibility> of the second factor. Both alternatives can hold: $7\mid14\cdot21$, and seven divides both $14$ and $21$.
In fact the property characterizes <prime numbers> among the <integers> greater than one. If $c$ is a <composite number>, choose $c=ab$ with $1<a,b<c$; then $c\mid ab$, but $c$ divides neither $a$ nor $b$. For several factors, repeated application of <Euclid's lemma> says that a <prime number> dividing their <product> divides at least one factor. In a <product> of <prime numbers>, that factor must equal it, because a <prime number> has no other <prime factor>. This is what prevents a different collection of <prime factors> from representing the same <positive integer> in the <fundamental theorem of arithmetic>.
Book VII, Proposition 30 of <Euclid's Elements> states the result in terms of a <prime number> measuring a <product>; its proof uses <coprimality> and <ratios>. The calculation using <Bézout's identity> above is a modern way to explain the same <divisibility> statement. https://mathcs.clarku.edu/~djoyce/java/elements/bookVII/propVII30.html[Euclid, Elements VII.30, translated text hosted by David Joyce]{ref}
Back to article page
