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