Euclidean division and base changes

Result: Euclidean division in $\mathbb N$.

Claim: for $a,b \in \N$ with $b > 0$ there exist unique $q,r\in \N$ such that $a=bq + r$ and $0 \leq r < b$. Pf: Consider the set $$ a – b\N = \{a, a-b, a-2b, a-3b, \dots\} $$ and intersect it with $\N$ to get $S := (a-b\N)\cap \N$. $S\subset \N$ so it is well ordered and therefore has a smallest element, say $r$, which is non-negative and $a-bq = r$ for some $q\in\N$. Furthermore, if $r \geq b$ then $a – bq > a – b(q+1) \geq 0$ which contradicts the minimality of $a-bq$ in $S$. Thus there at least exist $q,r\in\N$ with $0 \leq r < b$ such that $a = bq + r$ as desired.

For uniqueness, suppose that I also have $a = bq’ + r’$ with $0 \leq r’ < b$. Then
$$
0 = b(q-q’) + (r-r’)
$$
or equivalently
$$
r’ – r = b(q – q’).
$$
This means that $b | (r’-r)$. But $-(b-1) \leq r’-r \leq b-1$ so the only number in there that $b$ divides is zero which means $r=r’$. In the integers $xy=0 \implies x = 0 \vee y = 0$, and $b\neq 0$, so therefore $q=q’$. Thus the factorization both exists and is unique.

$\square$

I can use this to produce an algorithm for changing positive integers from one base to another. Expressed in base $b$, a number $a$ is given by
$$
a = \sum_{j=0}^k s_jb^j .
$$
For my algorithm I will first need to find $k$, which is one less than the number of digits in the number. I know that $a \geq b^k$ because that’s the smallest base $b$ number of length $k+1$, but also $a < b^{k+1}$ as that’s one bigger than the biggest length $k+1$ number. This means that I can uniquely specify $k$ via
$$
k = \max \{j \in \N :b^j \leq a \}
$$
and the set that the maximum is over is finite so the maximum will always exist and I can find it pretty easily algorithmically.

Armed with $k$ I can now proceed.

First, note that
$$
a = s_kb^k + \sum_{j=0}^{k-1}s_jb^j.
$$
For each $j$ $s_j \in \{0,\dots,b-1\}$ so
$$
\sum_{j=0}^{k-1}s_jb^j \leq (b-1)\sum_{j=0}^{k-1}b^j = (b-1)\frac{1 – b^k}{1-b} = b^k – 1
$$
so actually this is exactly for the form
$$
a = qb^k + r
$$
for $q,r\in \N$ with $0 \leq r < b^k$. This means that a single application of Euclidean division will give me both $s_k$ and the remainder.

Also note that I will have $q \in \{1,\dots,b-1\}$ since $r \leq b^k – 1 < a$, so $q=0$ isn’t an option. And if $q \geq b$ then $qb^k \geq b^{k+1} > a$ by the definition of $k$.

Now I have
$$
r = \sum_{j=0}^{k-1}s_jb^j = s_{k-1}b^{k-1} + \sum_{j=0}^{k-2}s_jb^j
$$
so I can apply Euclidean division to
$$
r = q’b^{k-1} + r’
$$
to get the next digit $q’ = s_{k-1}$ and the remainder $r’$ corresponding to the remaining $k-2$ digits. Recursively continuing this will let me successively extract each digit. It’s still the case that $q’ \leq b-1$ as otherwise this would mean $r \geq b^k$ which violates the upper bound on $r$, but now it is possible that $q’=0$ as $r$ could be considerably smaller than $b^{k-1}$.

A consequence of framing the base conversion this way is that I get the uniqueness of the base $b$ expression of $a$ almost for free, as $s_k$ and $r$ are the only integers with $0 \leq r < b^k$ such that $a = s_k b^k + r$, and so on, so each digit is neeessarily the unique solution to that step of the problem.

Here’s the algorithm in practice, implemented in python. The “divmod” function does the Euclidean division. The only reason that base 10 is special here is because all of this arithmetic is only available for base 10 numbers. If I had a Euclidean division for arbitrary base numbers then I wouldn’t be bound to base 10 at all. I may implement that in the future just for fun. But for now I made use of this for my general base changer by stepping into base 10 in the middle.

# determines the number of digits `num` will have
# once converted to `base` by finding the largest
# power of `base` such that it's not more than `num`.
def num_digits(num, base):
   ndigits = 0
   while base ** ndigits <= num:
      ndigits += 1
   return ndigits

# recursively applies Euclidean division via divmod
# to get the coefficient of each base power in the
# digit series.
def recur_euclid(digits, deg, a, base):
   if deg < 0:
      return digits
   q, r = divmod(a, base ** deg)
   digits.append(q)
   return recur_euclid(digits, deg - 1, r, base)

# wrapper for `recur_euclid` that prepares the inputs
def base10_to_other(num, base):
   assert num >= 0 and num == int(num)
   assert base >= 2 and base == int(base)
   return recur_euclid([], num_digits(num, base) - 1, num, base)

# converts a number in any appropriate base to base 10 via summation
def other_to_base10(digits, base):
   return sum([digits[-i] * base ** (i-1)
         for i in range(len(digits), 0, -1)])

# does a general change of base by stepping into base 10 in the middle
def base_converter(digits, input_base, target_base):
   return base10_to_other(other_to_base10(digits, input_base), target_base)