# Composite Number has Prime Factor

## Theorem

Let $a$ be a composite number.

Then there exists a prime number $p$ such that:

$p \divides a$

where $\divides$ means is a divisor of.

In the words of Euclid:

Any composite number is measured by some prime number.

## Proof

By definition of composite number:

$\exists b \in \Z: b \divides a$

If $b$ is a prime number then the proof is complete.

Otherwise $b$ is composite.

By definition of composite number:

$\exists c \in \Z: c \divides b$

and so:

$c \divides a$

Again, if $c$ is a prime number then the proof is complete.

Continuing in this manner, some prime number will be found which will divide the number before it.

This will be a divisor of $a$.

Because if not, then an infinite series of numbers will be divisors of $a$, each of which is less than the other.

This is impossible in numbers.

Hence the result.

$\blacksquare$

## Historical Note

This theorem is Proposition $31$ of Book $\text{VII}$ of Euclid's The Elements.