Houjun Liu


Let integer \(a,b \in \mathbb{Z}\), where \(b \neq 0\). We say \(b\) divides \(a\) (i.e. \(b|a\)) if there’s some \(m \in \mathbb{Z}\) such that \(a = bm\).

additional information

division algorithm

Let \(a,b \in \mathbb{Z}\), \(b > 0\). Then, there exists, uniquely, some \(q,r \in \mathbb{Z}\) such that \(a = bq + r\) with \(0 \leq r <b\).

“division with remainder”

You will note that, if \(a < b\), we can just say \(q = 0\).



Let us define some:

\begin{equation} S = \{a - bk: k \in \mathbb{Z}, a-bk \geq 0\} \end{equation}

We will note that this set is definitely non-empty:

  • If \(a \geq 0\), then \(a = a-b\cdot 0 \in S\)
  • If \(a < 0\) , then \(a-b(2a) = a(1-2b)\), we note that \(a < 0\) and since \(b >0\), \((1-2b) <0\), so \(a(1-2b) > 0\) and so \(a(1-2b) \in S\)

So by the WOP, \(S\) has a smallest element. Let us, by WOP, define \(r\) to be the smallest element in \(S\).

Therefore, we can make some \(r = a-bq \in S\). We also know that \(r\) is non-negative, as that is the constraint of \(S\). Finally, we have to ensure that \(r\) is the actual remainder, we have to ensure that \(r < b\).

Assume for contradiction \(r \geq b\). Then, \(r-b = (a-qb)-b = a-(q+1)b \geq 0\). Therefore, \(r-b \in S\). Yet, we said that \(r\) was the smallest element, reaching contradiction. Therefore, \(r<b\) . \(\blacksquare\)


Let us have:

\begin{equation} a = bq+r = bq’ + r' \end{equation}

Recall that, \(0 \leq r < b\). We desire that \(q = q’\), \(r = r’\).

WLOG let \(r \leq r’\). So, \(0 \leq r’ - r\). Both \(r’\) and \(r\) are remainders after dividing by \(b\), so \(r’ < b\) and \(r < b\). Therefore, we have:

\begin{equation} 0 \leq r’ - r < b \end{equation}

Now, recall that:

\begin{align} &bq+r = bq’ + r’\\ \Rightarrow\ &b(q-q’) = r’ - r \end{align}

Now, we have that \(b|(r’ - r)\). Hence, we have some positive \(r’ - r\), which is smaller than b, but which is divisible by \(b\). This forces us to conclude that \(r’ - r = 0\).

Given \(r’ = r\), now, we can see that \(q = q’\). \(\blacksquare\)