Composite Number has Prime Factor

From ProofWiki
Jump to: navigation, search

Theorem

Let $a$ be a composite number.

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

$p \mathop \backslash a$

where $\backslash$ means is a divisor of.


In the words of Euclid:

Any composite number is measured by some prime number.

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


Proof

By definition of composite number:

$\exists b \in \Z: b \mathop \backslash 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 \mathop \backslash b$

and so:

$c \mathop \backslash 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.


Sources