Pick a depth. Each prompt opens in your AI pre-loaded with the lesson. Click a row to preview the prompt.
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.
We say (read 'a divides b') if there exists an integer such that . The division algorithm says: for any integer and any positive integer , there exist unique integers (quotient) and (remainder) with and . The constraint is what makes and unique — without it you could shift by 1 and by and get another valid pair.
divmod_pos(1234, 17) and verify by hand that with . What are and ?divmod_pos(-47, 6) gives , . The C-style in many languages would give here — that's why this constraint matters.%// 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
}go run main.go