# Natural Number is Prime or has Prime Factor

Jump to navigation
Jump to search

## Theorem

Let $a$ be a natural number greater than $1$.

Then either:

- $a$ is a prime number

or:

- there exists a prime number $p \ne a$ such that $p \divides a$

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

In the words of Euclid:

*Any number either is prime or is measured by some prime number.*

(*The Elements*: Book $\text{VII}$: Proposition $32$)

## Proof

By definition of composite number $a$ is either prime or composite.

Let $a$ be prime.

Then the statement of the result is fulfilled.

Let $a$ be composite.

Then by Proposition $31$ of Book $\text{VII} $: Composite Number has Prime Factor:

- $\exists p: p \divides a$

where $p$ is a prime number.

The result follows by Proof by Cases.

$\blacksquare$

## Historical Note

This proof is Proposition $32$ of Book $\text{VII}$ of Euclid's *The Elements*.

## Sources

- 1926: Sir Thomas L. Heath:
*Euclid: The Thirteen Books of The Elements: Volume 2*(2nd ed.) ... (previous) ... (next): Book $\text{VII}$. Propositions