Exercise 2.3.5 (Euclidean algorithm)

How to think about the exercise. Terminological note: Tao calls this result "Euclidean algorithm", but Euclidean algorithm is most commonly used for a different algorithm. The common term used for the topic of this exercise seems to be Euclidean division.

For this exercise, the only slightly tricky part is proving the inductive step. Here, what turns out to work is to split into cases. But which cases? I think the easiest way to see is to look at some examples. Let’s take the following, where we fix $q=5$ and increment $n$ by one each time:

10 divided by 5 = 2 with remainder 0
11 divided by 5 = 2 with remainder 1
12 divided by 5 = 2 with remainder 2
13 divided by 5 = 2 with remainder 3
14 divided by 5 = 2 with remainder 4
15 divided by 5 = 3 with remainder 0

I hope you can see the pattern. At each increment of $n$, either the remainder goes up by 1 (in which case $m$ stays the same) or the remainder resets to 0 (in which case $m$ goes up by 1). What distinguishes the two cases? Well, the reset only happens when the remainder on the previous step is one less than the number we are dividing by, i.e. when $r+1=q$. For example, suppose we are at "14 divided by 5 = 2 with remainder 4". Then the remainder, 4, is one less than the number we are dividing by, which is 5.

Model solution. Let us fix $q$ and induct on $n$. For the case $n=0$, we must show that there are natural numbers $m,r$ such that $0\le r<q$ and $0=\mathit{mq}+r$. We can take $m=0$ and $r=0$. Indeed, we have $0\le 0<q$ (since $q$ is positive) and $0=0\times q+0$.

Now suppose inductively that there are natural numbers $m,r$ such that $0\le r<q$ and $n=\mathit{mq}+r$. We must show that there are natural numbers $m^{\prime },r^{\prime }$ such that $0\le r^{\prime }<q$ and $n+1=m^{\prime }q+r^{\prime }$.

We have two cases, $r+1=q$ and $r+1\ne q$. If $r+1=q$, we can take $m^{\prime }:=m+1$ and $r^{\prime }:=0$. Then $0\le r^{\prime }=0<q$ and we have $m^{\prime }q+r^{\prime }$ equal to $(m+1)q+0$ by definition of $m^{\prime },r^{\prime }$, which equals $\mathit{mq}+q$ by the distributive law, which equals $\mathit{mq}+r+1$ by using $q=r+1$, which equals $n+1$ by the inductive hypothesis $n=\mathit{mq}+r$. Thus $m^{\prime }q+r^{\prime }=n+1$ as required.

Now suppose $r+1\ne q$. In this case, $r<q$ from the inductive hypothesis gives $r+1\le q$, so $r+1<q$. So we can take $r^{\prime }:=r+1$ and $m^{\prime }:=m$. Now $0\le r^{\prime }<q$ by what we just showed, and $m^{\prime }q+r^{\prime }=\mathit{mq}+r+1=n+1$ by definition of $m^{\prime },r^{\prime }$ and the inductive hypothesis $n=\mathit{mq}+r$.

Source: Issa Rice’s blog.