Capstok — learn by doing

Why this matters

Every integer is the same mathematical object regardless of how we write it, but how we represent it determines the cost of every operation we perform. Computers use base 2 internally; we read base 10; cryptographers serialise large integers in base 16 or base 64; binary representations make multiplication by powers of 2 free; modular reduction by $2^k - 1$ is just digit summing in base $2^k$ . The point of this task is to internalise the division-algorithm view of base- $b$ representation: every integer $n \geq 0$ has a unique expansion $n = \sum d_i b^i$ with $0 \leq d_i < b$ , and that uniqueness is just the division algorithm applied recursively. Once you see that, you'll see why every fast modular-arithmetic algorithm — square-and-multiply for exponentiation, Montgomery reduction, Barrett reduction — is fundamentally about choosing the right base.

Demo

For any integer $n \geq 0$ and any base $b \geq 2$ , there is a unique sequence of digits $(d_k, d_{k-1}, \ldots, d_1, d_0)$ with , (unless ), and . The digits are computed by repeatedly dividing by and recording remainders — exactly the division algorithm, applied recursively.

n = \sum_{i=0}^{k} d_i \, b^i, \quad 0 \leq d_i < b, \quad d_k \neq 0 \text{ if } n > 0

Try it yourself

Convert 1729 to base 2, base 8, and base 16 by hand using repeated division. Verify each against to_base(1729, b) and against Python's bin/oct/hex.
Show numerically that for any $n$ , from_base(to_base(n, b), b) == n for several bases $b \in \{2, 3, 7, 16, 64\}$ . This is the round-trip that ratifies uniqueness.
Compute $123_{10}$ in base 4 by hand: , so digits are . Verify with .

Prompt your AI

Use these three in order. Each builds on the one before.

1. Basics & terminology

In one paragraph, explain what 'base $b$' means and how the division algorithm gives you the digits of any integer in any base. Why is the resulting digit sequence unique?

2. Why it works (the mechanism)

Walk me through *proving* that the base-$b$ representation of an integer is unique. The argument is a near-direct application of the division algorithm — show exactly how, by induction on the number of digits.

3. Advanced — application & what's next

Why does choosing $b = 2^{32}$ or $b = 2^{64}$ as the working base for a big-integer library (instead of base 10 or base 2) make multiplication and modular reduction much faster? Tie this to how Montgomery reduction and Barrett reduction work in real cryptographic libraries.

References

to_base(123, 4)

// main.go
package main

import "fmt"

// toBase returns the digits of n in base b, most significant first.
func toBase(n, b int) []int {
	if n == 0 {
		return []int{0}
	}
	var digits []int
	for n > 0 {
		digits = append(digits, n%b)
		n /= b
	}
	// reverse
	for i, j := 0, len(digits)-1; i < j; i, j = i+1, j-1 {
		digits[i], digits[j] = digits[j], digits[i]
	}
	return digits
}

// fromBase reconstructs the integer from digits in base b.
func fromBase(digits []int, b int) int {
	n := 0
	for _, d := range digits {
		n = n*b + d
	}
	return n
}

func main() {
	fmt.Println(toBase(255, 2))            // [1 1 1 1 1 1 1 1]
	fmt.Println(toBase(255, 16))           // [15 15]  -> ff
	fmt.Println(toBase(2024, 7))           // [5 6 6 1 1] -> 5*7^4 + 6*7^3 + 6*7^2 + 1*7 + 1
	fmt.Println(fromBase([]int{5, 6, 6, 1, 1}, 7)) // 2024

	// Go fmt verbs for common bases
	fmt.Printf("%b %x %o\n", 255, 255, 255) // 11111111 ff 377
	fmt.Println(255)                         // decimal
}

Run: go run main.go

Integer representations and bases