I think I'm in the process of (re-)discovering an interesting connection between Euclidean division, modular congruence, and numeral bases. In the back of our minds, let's store the example $14 \div 4 = 3R2$, which leads to the mod operator equation $14\ \%\ 4 = 2$ and the congruence $2 \equiv 14\ ($mod $4)$.
To start things off, we're clearly going to want to be in $\mathbb{Z}_4$, which we can write as the set of numbers $\{0, 1, 2, 3\}$, but is actually the set of congruence classes which have $0$, $1$, $2$, and $3$ as their principal representatives.
Let's consider the subset of each such congruence class containing its first $4$ (in general, the modulus) elements, starting with the principal representative. So in this case, our curtailed $\mathbb{Z}_4^* = \{\{0, 4, 8, 12\}, \{1, 5, 9, 13\}, \{2, 6, 10, 14\}, \{3, 7, 11, 15\}\}$. Two methods of accessing $\mathbb{Z}_4^*$ are now available; we can specify a congruence class and an element of that congruence class to land on a particular number $0$ through $15$, or we can specify the number $0$ through $15$ to land on a particular class-element pair. Applying our prepared example, specifying element $3$ of congruence class $2$ (both $0$-indexed) outputs $14$, the dividend. Inversely, specifying $14$ outputs $3$ and $2$, the quotient and remainder, respectively. This is the relation between $\mathbb{Z}_4^*$ and Euclidean division.
The relation to numeral bases easily follows; $14_{10} = 32_4$. For each number $0$ through $15$, its congruence class is the units digit, and the element of that congruence class the second-least-significant digit, of its base-$4$ representation.
However, so far we are restricted to dividends and base conversions of numbers $\leq 15$, and when I generalize one of the two, it is at the expense of the other. The Euclidean division relation can be generalized by operating in $\mathbb{Z}_4$ instead of $\mathbb{Z}_4^*$, where each congruence class is an infinite set, but this breaks the base algorithm. The base algorithm can be generalized by thinking of the numbers within the finite congruence classes of $\mathbb{Z}_4^*$ as finite congruence classes themselves, mod $16$ (in general, the original modulus squared). So we might say that $$_2\mathbb{Z}_4^* = \{\{\{0, 16, 32, 48\}, \{4, 20, 36, 52\}, \{8, 24, 40, 56\}, \{12, 28, 44, 60\}\}, \{\{1, 17, 33, 49\}, \{5, 21, 37, 53\}, \{9, 25, 41, 57\}, \{13, 29, 45, 61\}\}, \{\{2, 18, 34, 50\}, \{6, 22, 38, 54\}, \{10, 26, 42, 58\}, \{14, 30, 46, 62\}\}, \{\{3, 19, 35, 51\}, \{7, 23, 39, 55\}, \{11, 27, 43, 59\}, \{15, 31, 47, 63\}\}\}.$$ Now we can, for example, specify $19$, and find that it is element $1$ of intermediate-grouping $0$ of congruence class $3$. Thus, $19_{10} = 103_4$. To convert larger numbers, these new elements can also be treated as finite congruence classes to build $_3\mathbb{Z}_4^*$, and the pattern can continue recursively to build $_n\mathbb{Z}_4^*$. Unfortunately, this breaks the relation with Euclidean division, which only permits one divisor-part and one remainder-part, delimited by a single $R$.
Is there a better way to generalize the initial relation between Euclidean division, modular congruence, and numeral bases that preserves both connections? If not, what is the least-intrusive modification that could be made to Euclidean division to force it to survive the $_n\mathbb{Z}_4^*$ generalization (or would any such attempt turn Euclidean division into an isomorphism of base conversion)?
Best Answer
If you insist on using division, which outputs two numbers (quotient and remainder) so to speak, then you must use as many of them as you need if the original input is large, right? The obvious way is recursion:
$30 \div 4 = \color{red}{7} \, R \, \color{blue}{2}$
$\color{red}{7} \div 4 = \color{green}1 \, R \, \color{purple}3$
So $30_{10} = \color{green}1\color{purple}3\color{blue}2_4$.
...which is of course, in a sense, the definition or recipe for base $4$ representation.