Raising the bar

Division of one integer by another, with remainder

There are different approaches to explaining this topic. To see the difference, first try to read Theorems 6.1 and 6.2 in Abstract mathematics (M. Anthony, MT2116), then compare to the following approach.

Statement. For any integers $latex a$ and $latex b$ with $latex b>0$, there are unique integers $latex q$ and $latex r$ such that

(1) $latex a=bq+r$ and $latex 0\leq r<b$.

Proof. We want to cover the real line with half-open intervals of length $latex b.$ For $latex n\in Z$ put $latex x_{n}=bn$ and define intervals $latex \Delta _{n}=[bn,b\left(n+1)\right) .$ These intervals obviously are disjoint and cover all real numbers. Let $latex \Delta _{q}$ be the interval that contains $latex a.$ The number $latex a$ is the left end of the interval, $latex bq,$ plus some integer number $latex r.$ Since $latex bq\leq a=bq+r<bq+b,$ we have $latex 0\leq r<b$. Obviously, both $latex q$ and $latex r$ are unique.

The Euclidean algorithm

In Section 6.6 this algorithm is given without a proof. The proof is not  very complex and can be found here.  There you can also find a different version of the algorithm that converges faster, a statement that it is the best possible and an interesting visialization of the algorithm using tiles. Here we suggest a different visualization that is easier to use for practical calculations.

The main property of the algorithm written in the form

(2) $latex gcd(a,b)=gcd(b,r)$

($latex gcd$ stands for Greatest Common Divisor) is not good for visualizing. To better reflect its iterative nature, we can write (1) as $latex a_{1}=a_{2}q+a_{3}$ and then (2) becomes

(3) $latex gcd(a_{1},a_{2})=gcd(a_{2},a_{3}).$

Expanding the first three equations, we see that the calculations can be arranged as in the next table. After each division, we place the numbers $latex a_{k},a_{k+1}$ in the next row below their positions in the previous row and then fill out the rest of the formula with the quotient and remainder.

$latex \Large \left.\begin{array}{lllllllll}
a_{1} & = & a_{2}q_{1} & + & a_{3} & & & &\\
& & a_{2} & = & a_{3}q_{2} & + & a_{4} & &\\
& & & & a_{3} & = & a_{4}q_{3} & + & a_{5}\\
& & & & & & ... & ... & ...\end{array}\right.$