Quotient and Remainder to Number Base

Theorem

Let $n \in \Z: n > 0$ be an integer.

Let $n$ be expressed in base $b$:

$\displaystyle n = \sum_{j = 0}^m {r_j b^j}$

i.e.

$n = \left[{r_m r_{m-1} \ldots r_2 r_1 r_0}\right]_b$

Then:

• $\displaystyle \left \lfloor {\frac n b} \right \rfloor = \left[{r_m r_{m-1} \ldots r_2 r_1}\right]_b$
• $n \,\bmod\, b = r_0$

where:

• $\left \lfloor {.} \right \rfloor$ denotes the floor function;
• $n \,\bmod\, b$ denotes the modulo operation.

General Result

• $\displaystyle \left \lfloor {\frac n {b^s}} \right \rfloor = \left[{r_m r_{m-1} \ldots r_{s+1} r_s}\right]_b$
• $\displaystyle n \,\bmod\, {b^s} = \sum_{j = 0}^{s-1} {r_j b^j} = \left[{r_{s-1} r_{s-2} \ldots r_1 r_0}\right]_b$

where $s \in \Z: 0 \le s \le m$.

Proof

From the Quotient-Remainder Theorem, we have:

$\exists q, r \in \Z: n = q b + r$

where $0 \le b < r$.

We have that:

	\(\displaystyle \)	\(\displaystyle n\)	\(=\)	\(\displaystyle \sum_{j = 0}^m {r_j b^j}\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \sum_{j = 1}^m {r_j b^j} + r_0\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle b \sum_{j = 1}^m {r_j b^{j-1} } + r_0\)	\(\displaystyle \)

Hence we can express $n = q b + r$ where:

• $\displaystyle q = \sum_{j = 1}^m {r_{j} b^{j-1}}$
• $r = r_0$

where:

$\displaystyle \sum_{j = 1}^m {r_j b^{j-1}} = \left[{r_m r_{m-1} \ldots r_2 r_1}\right]_b$

The result follows from the definition of the modulo operation.

$\blacksquare$

Proof of General Result

Follows directly by induction on $s$.

Example

This result is often used in computer algorithms for converting a date (in $yyyymmdd$ format) into a date object with separate day, month and year.

Performing the above "mod and div" operations on $20100209$, we get:

	\(\displaystyle \)	\(\displaystyle 20100209 \,\bmod\, 100\)	\(=\)	\(\displaystyle 09\)	\(\displaystyle \)	which gives us the day
	\(\displaystyle \)	\(\displaystyle \left \lfloor {\frac {20100209} {100} } \right \rfloor\)	\(=\)	\(\displaystyle 201002\)	\(\displaystyle \)	which we use as input into the next pass
	\(\displaystyle \)	\(\displaystyle 201002 \,\bmod\, 100\)	\(=\)	\(\displaystyle 02\)	\(\displaystyle \)	which gives us the month
	\(\displaystyle \)	\(\displaystyle \left \lfloor {\frac {201002} {100} } \right \rfloor\)	\(=\)	\(\displaystyle 2010\)	\(\displaystyle \)	which gives us the year.