Unique prime factorization

A prime is a positive integer greater than one whose only positive divisors are one and itself. An integer greater than one that is not prime has a factorization into two smaller positive integers greater than one. Applying this observation repeatedly must stop, because the factors strictly decrease along any unfinished branch. Equivalently, strong induction on the integer proves existence of a finite product of primes.

The integer one is excluded from the primes for a structural reason: inserting extra factors of one would destroy a useful uniqueness statement. We treat one as the empty product, with all prime exponents zero. Negative integers require an additional sign; zero does not have a finite prime factorization of this form. State this domain before using exponent notation, rather than assuming that all integers fit the same representation.

The essential lemma says that if a prime p divides ab, it divides a or b. If p does not divide a, their gcd is one, so Bézout gives pu + av = 1. Multiplying by b shows b = pub + abv. Both terms on the right are divisible by p, proving that p divides b. This argument reveals the role of primality instead of treating the lemma as obvious.

Now compare two prime factorizations of the same positive integer. The first prime in one product divides the other product, so repeated use of the lemma forces it to divide one of the other prime factors. A prime dividing a prime must equal it. Cancel the matching factors in ordinary integer arithmetic and repeat. The products eventually contain exactly the same prime factors with the same multiplicities; their written order is irrelevant.

A positive divisor of n chooses, independently for each prime p, an exponent between zero and vₚ(n). Hence the number of positive divisors is the product of the quantities vₚ(n) + 1. This counting argument counts choices of exponents, not distinct primes alone. For a square, every prime exponent is even; multiplying two numbers adds corresponding exponents, which makes many parity arguments nearly automatic.

Unique factorization is a theorem about ordinary integers, not a promise that factoring large integers is computationally easy. Euclid computes a gcd without obtaining prime coordinates at all. Different tasks call for different representations: a factorization makes divisor structure transparent, while a remainder chain is often cheaper for a gcd. In more general rings, analogues of primes and irreducibles can behave differently; the proof here identifies the lemma that would need to survive.