Engineering / Mathematics — Integer Foundations
Consequences of Unique Factorization
What follows from the fundamental theorem: gcd and lcm via exponents, irrationality proofs, divisor counting and multiplicative structure.
Executive summary
Unique factorisation converts multiplicative questions about integers into combinatorial questions about exponent vectors. A positive integer becomes a finite tuple of prime exponents, multiplication becomes addition of tuples, and divisibility becomes componentwise comparison.
This reframing makes a range of results immediate that would otherwise require work.
Learning objectives
- Express gcd, lcm and divisibility in terms of exponent vectors.
- Prove irrationality results using factorisation parity arguments.
- Count divisors and recognise multiplicative structure.
01Integers as exponent vectors
Write v_p(n) for the exponent of the prime p in the factorisation of n, the p-adic valuation. Unique factorisation says n is determined by the function p → v_p(n), which is zero for all but finitely many primes.
v_p(mn) = v_p(m) + v_p(n) and m | n ⇔ v_p(m) ≤ v_p(n) for all p| Operation on integers | Operation on exponents |
|---|---|
| Multiplication | Componentwise addition |
| Divisibility | Componentwise ≤ |
| gcd | Componentwise minimum |
| lcm | Componentwise maximum |
| Perfect square | All exponents even |
From the minimum-maximum characterisation, the identity gcd(a,b) · lcm(a,b) = ab is immediate, since min(x,y) + max(x,y) = x + y componentwise.
02Irrationality by parity
Irrationality of √2
√2 is irrational.
Proof. Suppose √2 = a/b, so a² = 2b². Compare the exponent of 2 on each side: v₂(a²) = 2v₂(a) is even, while v₂(2b²) = 1 + 2v₂(b) is odd. No integer is both.
The argument generalises without effort. The square root of an integer is rational only when that integer is a perfect square, and more generally the k-th root of n is rational only when every exponent in the factorisation of n is divisible by k.
03Counting divisors
A divisor of n is determined by choosing, for each prime, an exponent between 0 and the exponent in n. The count follows immediately.
Divisor count
If n = p₁^e₁ ··· pₖ^eₖ then the number of positive divisors is τ(n) = (e₁ + 1) ··· (eₖ + 1).
Two structural observations follow. First, τ(n) is odd exactly when every exponent is even, that is, exactly when n is a perfect square — the reason perfect squares are the numbers with an odd number of divisors. Second, τ is multiplicative: τ(mn) = τ(m)τ(n) whenever gcd(m,n) = 1.
Multiplicativity is not an accident of this particular function. It reflects the fact that coprime integers have disjoint prime supports, so their exponent vectors combine independently. A large family of arithmetic functions inherits the property for the same reason.
04Frequently asked questions
Is v_p really a function on all integers?
On non-zero integers, yes. For 0 the convention v_p(0) = ∞ is used, which keeps the addition rule v_p(mn) = v_p(m) + v_p(n) valid and correctly makes every integer divide 0.
Does gcd · lcm = ab hold for more than two arguments?
No. For three or more integers the product of gcd and lcm is generally not the product of the arguments — the min and max of three values do not sum to their total. Inclusion-exclusion over the exponents gives the correct general identity.
Why is multiplicativity so common among arithmetic functions?
Because coprime arguments have disjoint sets of prime factors, so any function defined prime-by-prime from the factorisation automatically factors across a coprime product. Functions failing multiplicativity are those depending on the primes jointly rather than separately.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 8-12.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.