Capstok — learn by doing

Why this matters

The fundamental theorem of arithmetic is the statement that every integer $n > 1$ has a unique prime factorisation, up to ordering. 'Unique' is the load-bearing word: it's why divisibility, gcd, and lcm have clean prime-power formulas, why RSA encryption is reversible (because $\varphi(n)$ has a known structure when $n = pq$ ), and why number-theoretic identities translate into clean computational rules. The theorem looks obvious — of course $12 = 2^2 \cdot 3$ , what else could it be? — but the uniqueness is genuinely a theorem, and number systems where it fails (like $\mathbb{Z}[\sqrt{-5}]$ , where $6 = 2 \cdot 3 = (1 + \sqrt{-5})(1 - \sqrt{-5})$ ) drove the development of ideal theory. Knowing where the theorem holds and where it doesn't is the difference between number-theoretic intuition and number-theoretic competence.

Demo

The fundamental theorem of arithmetic: every integer $n > 1$ can be written as a product of primes $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ , and this factorisation is unique up to the order of the factors. Existence comes from strong induction (any composite splits into two smaller factors, recurse). Uniqueness depends on Euclid's lemma: if is prime and , then or — which itself follows from Bézout's identity.

\forall n > 1, \ \exists ! \ \text{multiset } \{(p_i, e_i)\} : n = \prod_i p_i^{e_i}, \ p_i \text{ prime}

Try it yourself

Factor 720 by hand: divide by the smallest prime repeatedly. You should get $720 = 2^4 \cdot 3^2 \cdot 5$ . Verify with factorint(720).
Factor 1001 — the answer reveals a nice pattern (it's the product of three small primes). Verify with sympy.
Use the prime-factor recipe to compute $\gcd(2520, 5400)$ and by hand, then check both against and .

References

math.gcd

math.lcm

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

import (
	"fmt"
	"sort"
)

// factorint returns the prime factorisation of n as a map prime -> exponent.
func factorint(n int) map[int]int {
	factors := map[int]int{}
	for d := 2; d*d <= n; d++ {
		for n%d == 0 {
			factors[d]++
			n /= d
		}
	}
	if n > 1 {
		factors[n]++
	}
	return factors
}

// primefactors returns the distinct primes of n in sorted order.
func primefactors(n int) []int {
	f := factorint(n)
	primes := make([]int, 0, len(f))
	for p := range f {
		primes = append(primes, p)
	}
	sort.Ints(primes)
	return primes
}

// reconstruct multiplies p^e for each entry — verifies round-trip.
func reconstruct(f map[int]int) int {
	n := 1
	for p, e := range f {
		for i := 0; i < e; i++ {
			n *= p
		}
	}
	return n
}

// gcdViaFactor: take the min exponent of each prime shared by both numbers.
func gcdViaFactor(a, b int) int {
	fa, fb := factorint(a), factorint(b)
	result := 1
	for p, ea := range fa {
		if eb, ok := fb[p]; ok {
			e := ea
			if eb < e {
				e = eb
			}
			for i := 0; i < e; i++ {
				result *= p
			}
		}
	}
	return result
}

func main() {
	fmt.Println(factorint(360))    // map[2:3 3:2 5:1]  -> 360 = 2^3 * 3^2 * 5
	fmt.Println(factorint(1071))   // map[3:2 7:1 17:1]
	fmt.Println(primefactors(360)) // [2 3 5] — the distinct primes

	// Reconstruct n from its factorisation
	fact := factorint(360)
	fmt.Println(reconstruct(fact)) // 360

	// gcd via prime factorisation
	fmt.Println(gcdViaFactor(360, 1071)) // 3
}

Run: go run main.go

Every Number Factors One Way (Fundamental Theorem of Arithmetic)

Why this matters

Demo

Try it yourself

References