*args **kwargs

Web Development Odds & Ends

Euclidean Division

Given any two integer quantities \(a\) and \(b\), with \(a > b\), it can be asked: into what multiple of \(b\) can \(a\) be divided?

For example, \(6 = 2 \times 3\) so six divided by three is two, and \(7 = 2\times3 + 1\) so seven divided by three is two "with one over".

This is a basic notion but its formal statement is important as it provides the foundation for the Euclidean Division Algorithm, Euclid's Lemma and Bezout's Identity, all of which are basic tools for studying divisibility and factorisation in \(\mathbb{Z}\).

Theorem (Euclidean Division): Let \(a\) and \(b\) be integers. If \(b > 0\), then there exist \(q, r\), also integers, such that

\begin{equation*} a = bq + r \text{ where } 0 \leq r < b \label{a}\tag{1} \end{equation*}

Proof [P. M. Cohn] It is easy to establish the result using rational numbers: let \(q\) be \(\lfloor \frac{a}{b} \rfloor\) the largest integer not exceeding \(\frac{a}{b}\), then

\begin{equation*} 0 \leq \left(\frac{a}{b}\right) - q < 1 \end{equation*}

and so

\begin{equation*} 0 \leq a - bq < b \end{equation*}

Hence the number \(r\) given by \(r = a - bq\) satisfies \((1)\).

But rather than invoking rational numbers, the result can also be proved via the Principle of Least Element. Let \(S\) be the set of all non-negative integers of the form \(a - bn\). The set \(S\) is not empty - for example, take \(n = -a^2\), then

\begin{equation*} a - bn = a + a^2b \geq 0 \end{equation*}

Therefore \(S\) has a least element \(r = a - bq\) say. By definition, \(r \geq 0\), and so we must only show that \(r < b\). Suppose on the contrary that \(r \geq b\), then

\begin{equation*} r - b = a - bq - b = a - b(q +1) \end{equation*}

which is an element of \(S\) smaller then \(r\), a contradiction. \(\Box\)

See Also:An alternative proof on wikipedia.