Capstok — learn by doing

Why this matters

Every result in number theory — and therefore every cryptographic primitive that builds on it — starts with the idea of one integer dividing another. The division algorithm is the precise statement that integer division always gives you a unique quotient and a unique remainder, and that remainder is the object every algorithm in this course will manipulate. RSA, Diffie-Hellman, elliptic-curve crypto, hash functions reducing modulo a prime, even the modulo operator your CPU runs on signed integers — all of them are claims about the remainder that this theorem guarantees exists and is unique. Get the statement and the proof of uniqueness in your hands now and the rest of the module is bookkeeping on top of it.

Demo

We say $a \mid b$ (read 'a divides b') if there exists an integer $k$ such that $b = ak$ . The division algorithm says: for any integer $a$ and any positive integer $b$ , there exist unique integers $q$ (quotient) and $r$ (remainder) with $a = bq + r$ and $0 \leq r < b$ . The constraint $0 \leq r < b$ is what makes $q$ and $r$ unique — without it you could shift $q$ by 1 and $r$ by $-b$ and get another valid pair.

\forall a \in \mathbb{Z}, \ b \in \mathbb{Z}_{>0}, \ \exists ! \ (q, r) \in \mathbb{Z}^2 : \ a = bq + r, \ 0 \leq r < b

Try it yourself

Run divmod_pos(1234, 17) and verify by hand that $1234 = 17q + r$ with $0 \leq r < 17$ . What are $q$ and $r$ ?
Confirm that divmod_pos(-47, 6) gives , . The C-style in many languages would give here — that's why this constraint matters.

Prompt your AI

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

1. Basics & terminology

In one paragraph, explain what 'a divides b' means for integers and give an everyday example. Then state the division algorithm in your own words — what is it really claiming, and why is the uniqueness condition $0 \leq r < b$ essential?

2. Why it works (the mechanism)

Walk me step by step through how to *prove* the division algorithm: existence (use the well-ordering principle on the set $\{a - bk : k \in \mathbb{Z}, a - bk \geq 0\}$) and uniqueness (assume two representations and derive a contradiction). Where does each property of $\mathbb{Z}$ enter?

3. Advanced — application & what's next

How does the division algorithm generalise to negative divisors, to Gaussian integers $\mathbb{Z}[i]$, and to the polynomial ring $\mathbb{F}_p[x]$? In each case, what plays the role of $0 \leq r < b$, and why does that choice make the quotient and remainder unique?

References

(q, r) = (-8, 1)

%

// main.go — run: go run main.go
package main

import "fmt"

// divmodPos implements the division algorithm for positive b.
// Returns (q, r) such that a == b*q + r and 0 <= r < b.
func divmodPos(a, b int) (int, int) {
	if b <= 0 {
		panic("division algorithm requires b > 0")
	}
	// Go's % can return negative remainders for negative a;
	// adjust to get the mathematical (non-negative) remainder.
	q := a / b
	r := a % b
	if r < 0 {
		r += b
		q--
	}
	if a != b*q+r || r < 0 || r >= b {
		panic("invariant violated")
	}
	return q, r
}

// divides reports whether a divides b (a | b).
func divides(a, b int) bool {
	if a != 0 {
		return b%a == 0
	}
	return b == 0
}

func main() {
	fmt.Println(divmodPos(47, 6))   // 7 5   because 47 = 6*7 + 5
	fmt.Println(divmodPos(-47, 6))  // -8 1  because -47 = 6*-8 + 1
	fmt.Println(divmodPos(0, 6))    // 0 0

	fmt.Println(divides(7, 49)) // true
	fmt.Println(divides(7, 50)) // false
}

Run: go run main.go

Divisibility and the division algorithm