# Euclid's Lemma for Prime Divisors

## Contents

## Lemma

Let $p$ be a prime number.

Let $a$ and $b$ be integers such that:

- $p \divides a b$

where $\divides$ means **is a divisor of**.

Then $p \divides a$ or $p \divides b$.

### General Result

Let $p$ be a prime number.

Let $\displaystyle n = \prod_{i \mathop = 1}^r a_i$.

Then if $p$ divides $n$, it follows that $p$ divides $a_i$ for some $i$ such that $1 \le i \le r$.

That is:

- $p \divides a_1 a_2 \ldots a_n \implies p \divides a_1 \lor p \divides a_2 \lor \cdots \lor p \divides a_n$

### Corollary

Let $p, p_1, p_2, \ldots, p_n$ be primes such that:

- $p \divides \displaystyle \prod_{i \mathop = 1}^n p_i$

Then:

- $\exists i \in \closedint 1 n: p = p_i$

## Proof 1

We have that the integers form a Euclidean domain.

Then from Irreducible Elements of Ring of Integers we have that the irreducible elements of $\Z$ are the primes and their negatives.

The result then follows directly from Euclid's Lemma for Irreducible Elements.

$\blacksquare$

## Proof 2

Let $p \divides a b$.

Suppose $p \nmid a$.

Then from the definition of prime:

- $p \perp a$

where $\perp$ indicates that $p$ and $a$ are coprime.

Thus from Euclid's Lemma it follows that:

- $p \divides b$

Similarly, if $p \nmid b$ it follows that $p \divides a$.

So:

- $p \divides a b \implies p \divides a$ or $p \divides b$

as we needed to show.

$\blacksquare$

## Proof 3

Let $p \divides a b$.

Suppose $p \nmid a$.

Then by Proposition $29$ of Book $\text{VII} $: Prime not Divisor implies Coprime:

- $p \perp a$

As $p \divides a b$, it follows by definition of divisor:

- $\exists e \in \Z: e p = a b$

So by Proposition $19$ of Book $\text{VII} $: Relation of Ratios to Productsâ€Ž:

- $p : a = b : e$

But as $p \perp a$, by:

and:

it follows that:

- $p \divides b$

Similarly, if $p \perp b$ then $p \divides a$.

Hence the result.

$\blacksquare$

## Also presented as

Some sources present this as:

Let $p$ be a prime number.

Let $a$ and $b$ be integers such that:

- $a b \equiv 0 \pmod p$

Then either $a \equiv 0 \pmod p$ or $b \equiv 0 \pmod p$.

## Also known as

Some sources give the name of this as **Euclid's first theorem**.

## Source of Name

This entry was named for Euclid.

## Also see

Some sources use this property to **define** a prime number.

## Sources

- 1965: J.A. Green:
*Sets and Groups*... (previous) ... (next): Chapter $2$. Equivalence Relations: Exercise $7$ - 1979: G.H. Hardy and E.M. Wright:
*An Introduction to the Theory of Numbers*(5th ed.) ... (previous) ... (next): $\text I$: The Series of Primes: $1.3$ Statement of the fundamental theorem of arithmetic: Theorem $3$ - 1992: George F. Simmons:
*Calculus Gems*... (previous) ... (next): Chapter $\text {B}.16$: The Sequence of Primes: Problem $1 \ \text{(b)}$