Odd Divisor of Even Number also divides its Half

From ProofWiki
Jump to navigation Jump to search


Let $a, b \in \Z$ be integers.

Let $a$ be odd and $b$ be even.


$a \divides b$

where $\divides$ denotes divisibility.


$a \divides \dfrac b 2$

In the words of Euclid:

If an odd number measure an even number, it will also measure the half of it.

(The Elements: Book $\text{IX}$: Proposition $30$)


By definition of an even number:

$\exists r \in \Z: b = 2 r$

By definition of an odd number:

$\exists s \in \Z: a = 2 s + 1$


$a \divides 2 \iff a = \pm 1$

in which case from One Divides all Integers:

$a \divides \dfrac b 2$

We have that:

$a \divides 2 r$

and so by Euclid's Lemma:

$a \divides r = \dfrac b 2$


Historical Note

This proof is Proposition $30$ of Book $\text{IX}$ of Euclid's The Elements.