Capstok — learn by doing

Why this matters

The greatest common divisor of two integers is the single number that captures their shared multiplicative structure, and it shows up everywhere downstream: when you reduce a fraction, when you check whether an element has a multiplicative inverse modulo $n$ , when you compute the order of an element in a cyclic group, when RSA picks a public exponent coprime to $\varphi(n)$ . The reason to define it carefully now — as 'the largest positive integer dividing both' — is that the next two tasks will give you a recursive identity and an algorithm that compute it without any factoring. That algorithm is the workhorse of computational number theory, and this definition is what it computes.

Demo

The greatest common divisor $\gcd(a, b)$ of two integers, not both zero, is the largest positive integer $d$ that divides both. By convention $\gcd(0, 0) = 0$ and $\gcd(a, 0) = |a|$ . Two integers are coprime (or relatively prime) when $\gcd(a, b) = 1$ .

\gcd(a, b) = \max\{d \in \mathbb{Z}_{>0} : d \mid a \text{ and } d \mid b\}, \quad \gcd(a, b) = \gcd(b, a) = \gcd(|a|, |b|)

Try it yourself

Run math.gcd(1071, 462) and verify on paper that 21 divides both, and that no integer between 22 and 462 divides both.
List all common divisors of 60 and 84 by hand: $\{1, 2, 3, 4, 6, 12\}$ . Confirm math.gcd(60, 84) == 12 matches the largest.
Compute gcd_naive(10**6, 10**6 - 1) and time it; then compute math.gcd(10**6, 10**6 - 1). The naive version should be visibly slower — that motivates Euclid's algorithm in the next task.
Verify three properties on examples of your own choosing: $\gcd(a, b) = \gcd(b, a)$ , , and .

References

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

import (
	"fmt"
	"math/big"
)

func gcdNaive(a, b int) int {
	if a < 0 {
		a = -a
	}
	if b < 0 {
		b = -b
	}
	if a == 0 && b == 0 {
		return 0
	}
	smaller := a
	if b < smaller {
		smaller = b
	}
	result := 1
	for d := 1; d <= smaller; d++ {
		if a%d == 0 && b%d == 0 {
			result = d
		}
	}
	return result
}

func main() {
	gcd := func(a, b int64) int64 {
		return new(big.Int).GCD(nil, nil, big.NewInt(a), big.NewInt(b)).Int64()
	}

	fmt.Println(gcd(48, 18))     // 6
	fmt.Println(gcd(1071, 462))  // 21
	fmt.Println(gcd(13, 27))     // 1   -> 13 and 27 are coprime
	fmt.Println(gcd(0, 17))      // 17
	fmt.Println(gcd(-48, 18))    // 6   -> sign-insensitive

	// Naive definition-based gcd (don't use this for big numbers)
	fmt.Println(gcdNaive(48, 18)) // 6 — agrees with big.Int.GCD
}

Run: go run main.go

Greatest common divisor

Why this matters

Demo

Try it yourself

References