Division with Remainder

The division with remainder is also known as the Euclidean division.

Let \(a\) and \(b\) two non negative integers with \(b\neq 0\). If we divide \(a\) by \(b\) we get a quotient \(q\) and a remainder \(r\), both integers, such that:

\[a=bq+r\]

We typically select values for the quotient \(q\) and remainder \(r\) such that we obtain the smallest non-negative remainder for the division.

Theorem 1: There always exists an \(r\) such that \(0\leq r< b\).

Proof: Assume we have an \(r\) such that \(r>b\). Then, we can replace \(r\) by \(r=r'+b\). Substituting this in the equation above yields

\[a=bq+(r'+b) = bq+b+r'=b(q+1)+r'\]

We repeat this substituation process until we have \(r<b\).

Theorem 2: Under the assumption that \(0\leq r < b\) the quotient \(q\) and remainder \(r\) are unique for \(a\) and \(b\) (in particular, there is no remainder that is smaller than \(r\)).

Proof: Let’s assume we have the quotients \(q_1\) and \(q_2\), and remainder \(r_1\) and \(r_2\) with \(0\leq r_1, r_2<b\). Then,

\[a=bq_1+r_1\quad \text{and} \quad a=bq_2 + r_2\]

It follows that

\[bq_1+r_1 = bq_2+r_2\]

and after some rearrangement, we get

\[r_1-r_2 = b(q_2-q_1)\]

Due to the assumption \(0\leq r_1,r_2<b\), it follows that \(\mid r_1-r_2\mid <b\). This implies that \(\mid q_2-q_1\mid\) must be smaller than 1. As the quotient is an integer, \(q_2-q_1\) must be equal to zero, leading to \(q_2=q_1\). Since \(q_2-q_1=0\), it follows that \(r_1-r_2=0\), hence \(r_1=r_2\).