Pick a depth. Each prompt opens in your AI pre-loaded with the lesson. Click a row to preview the prompt.
The Euclidean algorithm computes in steps, no factoring required, and it's one of the oldest non-trivial algorithms ever recorded — Euclid wrote it down around 300 BC. It matters now because every modern public-key crypto system (RSA, ECDSA, EdDSA, Diffie-Hellman) needs gcds and modular inverses on huge integers, and the only reason that's tractable is this algorithm. The trick is the identity , which collapses the problem into a tail-recursive shrinking sequence. Once you've internalized why that identity is true, you've also internalized the central move of computational number theory: replace integers with their remainders, repeatedly, until the answer is staring at you.
The Euclidean algorithm repeatedly applies the identity , terminating when the second argument becomes 0. At that point is the answer. Why is the identity true? Any common divisor of and also divides , and vice versa, so the set of common divisors of equals the set of common divisors of — and therefore the element of those sets is the same.
gcd_trace output.gcd_trace(2024, 748) and count how many steps it takes. Predict the count for gcd_trace(2 * 2024, 2 * 748) before running — should be the same number of steps, since scaling by 2 doesn't change the algorithm's structure.gcd_trace(89, 55) and observe that every quotient is 1. Lamé's theorem says this is the slowest input shape — the number of steps is bounded by .gcd_rec(a, b) = a if b == 0 else gcd_rec(b, a % b) and verify it gives the same answer as the iterative version on 10 random pairs.// main.go
package main
import (
"fmt"
)
func gcd(a, b int) int {
if a < 0 {
a = -a
}
if b < 0 {
b = -b
}
for b != 0 {
a, b = b, a%b
}
return a
}
// Trace gcd(1071, 462)
func gcdTrace(a, b int) int {
if a < 0 {
a = -a
}
if b < 0 {
b = -b
}
for b != 0 {
q, r := a/b, a%b
fmt.Printf("%d = %d*%d + %d\n", a, b, q, r)
a, b = b, r
}
return a
}
func main() {
fmt.Println("gcd =", gcdTrace(1071, 462))
// 1071 = 462*2 + 147
// 462 = 147*3 + 21
// 147 = 21*7 + 0
// gcd = 21
}
go run main.go