Go Guide

DP, math & design · Lesson 41 of 62 · about 55 min

Math & number theory

GCD and LCM, primes with the sieve, factorization, fast modular exponentiation, modular inverses and combinations, overflow, and math/big for numbers that do not fit.

pkg.go.dev: math/big ↗cp-algorithms: Binary exponentiation ↗
On this page · 8 sections
  1. 01GCD and LCM
  2. 02Primes
  3. 03Modular arithmetic
  4. 04Overflow, and numbers bigger than int64
  5. 05A touch of geometry: orientation
  6. 06Summary
  7. 07Check your understanding
  8. 08Practice in Go

GCD and LCM#

The greatest common divisor of a and b is the largest number dividing both. Euclid's algorithm: gcd(a, b) = gcd(b, a mod b), and gcd(a, 0) = a. Any number dividing both a and b also divides a mod b, so the answer is unchanged while the numbers shrink fast.

gcd(1071, 462) → gcd(462, 147) → gcd(147, 21) → gcd(21, 0) = 21

The least common multiple follows: lcm(a, b) = a / gcd(a, b) * b. Divide first to keep the intermediate value small.

Uses: simplifying fractions, normalizing slopes so (2, 4) and (1, 2) compare equal, finding when two repeating schedules coincide (every 6 days and every 8 days line up every lcm(6, 8) = 24 days).

Primes#

Trial division checks divisors up to √n: if n had no divisor ≤ √n, it has none at all, because divisors come in pairs d and n/d. That is O(√n) per number.

To find all primes up to n, the sieve of Eratosthenes crosses out multiples of each prime, starting at p² (smaller multiples have a smaller prime factor and are already crossed out). Total work: O(n log log n), practically linear.

Trial division also gives factorization: divide out each factor as long as it divides, and whatever remains above 1 at the end is itself prime.

Modular arithmetic#

When answers get astronomically large ("number of ways to climb 10,000 stairs"), problems ask for the result modulo a prime, usually 1_000_000_007. The rules:

OperationSafe form in Go (values already in [0, m))
add(a + b) % m
subtract((a - b) % m + m) % m, because Go's % keeps the sign
multiplya * b % m (fits in int64 when m ≈ 10⁹)
divide by bmultiply by the inverse of b

Fast exponentiation

a^n with n multiplications is too slow for n = 10¹⁸. Binary exponentiation squares instead: a^13 = a^8 · a^4 · a^1, because 13 is 1101 in binary. Square the base once per bit and multiply it into the result whenever the bit is 1: O(log n).

Modular inverse

There is no division modulo m, but if m is prime, every non-zero a has an inverse: by Fermat's little theorem, a^(m-1) ≡ 1 (mod m), so a^(m-2) is the inverse. Combined with precomputed factorials, this gives C(n, k) mod p in O(1) per query.

numbertheory.go
Go
package main
 
import "fmt"
 
const MOD = 1_000_000_007
 
func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}
 
func lcm(a, b int) int { return a / gcd(a, b) * b }
 
func isPrime(n int) bool {
	if n < 2 {
		return false
	}
	for d := 2; d*d <= n; d++ {
		if n%d == 0 {
			return false
		}
	}
	return true
}
 
func sieve(n int) []int {
	composite := make([]bool, n+1)
	var primes []int
	for p := 2; p <= n; p++ {
		if composite[p] {
			continue
		}
		primes = append(primes, p)
		for m := p * p; m <= n; m += p {
			composite[m] = true
		}
	}
	return primes
}
 
func factorize(n int) map[int]int {
	f := map[int]int{}
	for d := 2; d*d <= n; d++ {
		for n%d == 0 {
			f[d]++
			n /= d
		}
	}
	if n > 1 {
		f[n]++ // what is left is a prime
	}
	return f
}
 
// powMod computes base^exp % mod by squaring.
func powMod(base, exp, mod int) int {
	result := 1
	base %= mod
	for exp > 0 {
		if exp&1 == 1 {
			result = result * base % mod
		}
		base = base * base % mod
		exp >>= 1
	}
	return result
}
 
// Precomputed factorials make C(n, k) mod p O(1) per query.
type Comb struct{ fact, inv []int }
 
func NewComb(n int) *Comb {
	fact := make([]int, n+1)
	inv := make([]int, n+1)
	fact[0] = 1
	for i := 1; i <= n; i++ {
		fact[i] = fact[i-1] * i % MOD
	}
	inv[n] = powMod(fact[n], MOD-2, MOD) // Fermat inverse, once
	for i := n; i > 0; i-- {
		inv[i-1] = inv[i] * i % MOD // 1/(i-1)! = i / i!
	}
	return &Comb{fact, inv}
}
 
func (c *Comb) C(n, k int) int {
	if k < 0 || k > n {
		return 0
	}
	return c.fact[n] * c.inv[k] % MOD * c.inv[n-k] % MOD
}
 
func main() {
	fmt.Println("gcd(1071, 462) =", gcd(1071, 462), " lcm(6, 8) =", lcm(6, 8))
	fmt.Println("97 prime?", isPrime(97), " 91 prime?", isPrime(91))
	fmt.Println("primes up to 50:", sieve(50))
	fmt.Println("count up to 1,000,000:", len(sieve(1_000_000)))
	fmt.Println("360 =", factorize(360))
 
	fmt.Println("2^10 mod 1000 =", powMod(2, 10, 1000))
	fmt.Println("2^(10^18) mod 1e9+7 =", powMod(2, 1_000_000_000_000_000_000, MOD))
	inv3 := powMod(3, MOD-2, MOD)
	fmt.Println("inverse of 3:", inv3, " check 3*inv % MOD =", 3*inv3%MOD)
 
	c := NewComb(1000)
	fmt.Println("C(5,2) =", c.C(5, 2), " C(1000,500) mod p =", c.C(1000, 500))
	fmt.Println("unique paths in a 3x7 grid = C(8,2) =", c.C(8, 2))
 
	fmt.Println("Go's % keeps the sign:", -7%3, " fixed:", ((-7%3)+3)%3)
}
Output
gcd(1071, 462) = 21  lcm(6, 8) = 24
97 prime? true  91 prime? false
primes up to 50: [2 3 5 7 11 13 17 19 23 29 31 37 41 43 47]
count up to 1,000,000: 78498
360 = map[2:3 3:2 5:1]
2^10 mod 1000 = 24
2^(10^18) mod 1e9+7 = 719476260
inverse of 3: 333333336  check 3*inv % MOD = 1
C(5,2) = 10  C(1000,500) mod p = 159835829
unique paths in a 3x7 grid = C(8,2) = 28
Go's % keeps the sign: -1  fixed: 2

powMod(2, 10¹⁸, MOD) finishes instantly because it needs only about 60 squarings. factorize prints a map; fmt sorts map keys when printing, so the output is stable.

Overflow, and numbers bigger than int64#

int in Go is 64 bits on all modern platforms: up to about 9.2 × 10¹⁸. Overflow wraps silently (lesson 2). Defenses:

  • reduce modulo m after every multiplication, not once at the end;
  • check before multiplying: a > math.MaxInt / b means a * b would overflow;
  • use math/bits.Mul64 to get the full 128-bit product of two uint64s;
  • use math/big when you genuinely need huge exact numbers (cryptography, exact factorials, money in some systems).
bignum.go
Go
package main
 
import (
	"fmt"
	"math"
	"math/big"
	"math/bits"
)
 
func main() {
	x := math.MaxInt64
	fmt.Println("MaxInt64 + 1 wraps to", x+1)
 
	hi, lo := bits.Mul64(1<<63, 4) // the 128-bit product, as two halves
	fmt.Println("2^63 * 4 as 128 bits: hi =", hi, "lo =", lo)
 
	f := big.NewInt(1)
	for i := int64(2); i <= 30; i++ {
		f.Mul(f, big.NewInt(i)) // math/big methods write into the receiver
	}
	fmt.Println("30! =", f)
 
	p, _ := new(big.Int).SetString("170141183460469231731687303715884105727", 10) // 2^127 - 1
	fmt.Println("2^127-1 probably prime:", p.ProbablyPrime(20))
 
	r := new(big.Rat).SetFrac64(1, 3)
	r.Add(r, big.NewRat(1, 6))
	fmt.Println("1/3 + 1/6 =", r) // exact, unlike float64
}
Output
MaxInt64 + 1 wraps to -9223372036854775808
2^63 * 4 as 128 bits: hi = 2 lo = 0
30! = 265252859812191058636308480000000
2^127-1 probably prime: true
1/3 + 1/6 = 1/2

A touch of geometry: orientation#

Many geometry problems reduce to one question: going from point A to B, is point C on the left, on the right, or straight ahead? The cross product answers it with integers, no floating point:

Go
func orient(ax, ay, bx, by, cx, cy int) int {
	return (bx-ax)*(cy-ay) - (by-ay)*(cx-ax) // > 0 left turn, < 0 right turn, 0 collinear
}

Convex hulls, "do these segments intersect?", and polygon area (the shoelace formula is a sum of cross products) all build on it.

Summary#

  • gcd(a, b) = gcd(b, a mod b); lcm = a / gcd * b.
  • Trial division checks up to √n; the sieve finds all primes up to n in about linear time.
  • Work modulo a prime with the safe forms; fix negative remainders.
  • Binary exponentiation computes powers in O(log n); Fermat gives inverses for prime moduli.
  • Precomputed factorials and inverse factorials give combinations in O(1).
  • Use math/bits for 128-bit products and math/big for exact huge numbers.

Check your understanding

Answer before scrolling back up. If you miss one, reread the matching section, then try again.

  1. Q1.Euclid's algorithm computes gcd(a, b) as:

  2. Q2.Why does the sieve start crossing out multiples of p at p²?

  3. Q3.Fast exponentiation computes a^n in how many multiplications?

  4. Q4.When the modulus p is prime, the modular inverse of a is:

  5. Q5.Why compute (a * b) % m with values already reduced below m = 1e9+7?

Practice in Go

Write a table test first, then the solution. On LeetCode, choose Go as the language. Open a hint only after 15 minutes stuck.

Finished this lesson?

Mark it done to track your progress. It is saved in this browser only.