Natural Number is Prime or has Prime Factor

From ProofWiki
Jump to: navigation, 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 \mathop \backslash a$

where $\backslash$ means 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 \mathop \backslash a$

where $p$ is a prime number.


The result follows by Proof by Cases.

$\blacksquare$


Historical Note

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


Sources