Natural Number Divisor or Multiple of Divisor of Another

From ProofWiki

Jump to: navigation, search

Theorem

As Euclid defined it:

Any (natural) number is either a part or parts of any (natural) number, the less of the greater.

Let $A, BC$ be two (natural) numbers and let $BC < A$.

We need to show that $BC$ is either a part or parts of $A$.

That is, either $BC$ is a divisor of $A$, or it is a multiple of some divisor of $A$.

$A$ and $BC$ are either coprime or they are not.

First, suppose $A$ and $BC$ are coprime.

Then if $BC$ be divided into the units in it, each unit of $BC$ will be some part of $A$, so that $BC$ is parts of $A$.

Next, let $A$ and $BC$ not be coprime.

Then $BC$ either divides $A$ or it does not.

If $BC$ divides $A$ then $BC$ is a part of $A$.

But if not, then let $D$ be the GCD of $A$ and $BC$ by Euclid's algorithm.

Let $BC$ be divided into the numbers equal to $D$, namely $BE, EF, FC$.

Then each of the numbers $BE, EF, FC$ is also a part of $A$.

That is, $BC$ is a parts of $A$.

$\blacksquare$

This is Proposition 4 of Book VII of Euclid's The Elements.