Fundamental Theorem of Arithmetic

The fundamental theorem of arithmetic is a foundational result in number theory: every integer greater than 1 can be expressed as a product of prime numbers, and that expression is unique except for the order of the factors. It establishes both the existence of prime factorizations and the uniqueness of the primes and their multiplicities. (courses.csail.mit.edu)

Statement and meaning

For every integer $n>1$ , there are distinct primes $p_1<p_2<\cdots<p_r$ and positive integers $a_1,\ldots,a_r$ such that

n=p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}.

With the primes placed in increasing order, both the primes and their exponents are uniquely determined by $n$ . This expression is called the prime-power decomposition of $n$ . (faculty.etsu.edu)

For example,

360=2^3\cdot3^2\cdot5.

The theorem means that every decomposition of 360 into prime factors contains exactly three factors equal to 2, two equal to 3, and one equal to 5. Different orders of multiplication do not count as different prime factorizations. By contrast, factorizations into arbitrary integers need not be unique: $12=2\cdot6=3\cdot4$ . These examples illustrate the distinction between prime factorization and unrestricted factorization. (courses.csail.mit.edu)

The standard statement excludes 1. Under the convention that a product with no factors equals 1, the theorem can also be stated for every positive integer, with 1 represented by the empty product. Negative integers are handled by factoring their absolute values and attaching a minus sign. In the ring of integers, $1$ and $-1$ are units: they possess multiplicative inverses within the ring. Uniqueness for nonzero integers is therefore understood up to order and multiplication by units. (en.wikipedia.org)

Proof

The two parts of the theorem require different arguments. Existence follows from the fact that composite positive integers split into smaller factors. Uniqueness depends on a stronger property of prime divisibility. (web.stanford.edu)

Existence

A proof by strong mathematical induction establishes existence.

The integer 2 is prime, so it already has a prime factorization. Suppose every integer between 2 and $n-1$ has a prime factorization. If $n$ is prime, its factorization consists of $n$ alone. Otherwise,

n=ab,\qquad 1<a<n,\quad 1<b<n.

Both $a$ and $b$ have prime factorizations by the induction hypothesis. Multiplying those factorizations gives one for $n$ . (web.stanford.edu)

Equivalently, repeated splitting of composite factors must terminate: each split replaces a factor by smaller positive integers, and an indefinitely decreasing sequence of positive integers is impossible. This termination principle is closely connected with the well-ordering principle. (cs.clarku.edu)

Euclid’s lemma

Euclid’s lemma states that if a prime $p$ divides a product $ab$ , then $p$ divides at least one of $a$ and $b$ :

p\mid ab\quad\Longrightarrow\quad p\mid a\ \text{or}\ p\mid b.

Here $p\mid a$ means that $a$ is an integer multiple of $p$ . To prove the lemma, suppose $p\nmid a$ . Since $p$ is prime, the greatest common divisor of $p$ and $a$ is then 1. Bézout’s identity, obtainable from the Euclidean algorithm, supplies integers $x,y$ satisfying

xp+ya=1.

Multiplying by $b$ gives

xpb+yab=b.

Both terms on the left are divisible by $p$ , so $p\mid b$ . Repeated application extends the lemma to any finite product: a prime dividing the product must divide at least one factor. (courses.csail.mit.edu)

Uniqueness

Suppose an integer has two prime factorizations,

n=p_1p_2\cdots p_k=q_1q_2\cdots q_m,

where repeated primes are written separately. Since $p_1$ divides the product on the right, Euclid’s lemma implies that it divides some $q_j$ . Because $q_j$ is prime, $p_1=q_j$ . Rearrange the factors and cancel this common prime.

The same argument applies to the remaining products. Neither side can run out of factors before the other, since a nonempty product of primes is greater than 1. Consequently $k=m$ , and the two lists contain exactly the same primes with the same multiplicities. (itamar.web.illinois.edu)

Historical development

Important ingredients appear in Euclid’s Elements. Book VII, Proposition 30 states the prime-divisibility property now called Euclid’s lemma. Book IX, Proposition 14 gives a related result concerning the least number divisible by specified primes. These propositions provide ancient foundations for unique factorization, although they should not simply be identified with the complete modern statement. (mathcs.clarku.edu)

Carl Friedrich Gauss explicitly stated and proved uniqueness in Article 16 of Disquisitiones Arithmeticae, published in 1801. He treated the existence of prime factorizations as evident rather than presenting a separate proof of it. The historical development thus distinguishes elementary knowledge of prime decomposition from explicit recognition and proof of its uniqueness. (la.wikisource.org)

Consequences and uses

Divisibility and greatest common divisors

Prime factorization reduces questions of divisibility to comparisons of exponents. Write two positive integers using a common list of primes,

a=\prod_p p^{\alpha_p}, \qquad b=\prod_p p^{\beta_p},

where absent primes have exponent zero and only finitely many exponents are nonzero. Then

a\mid b \quad\Longleftrightarrow\quad \alpha_p\leq\beta_p\text{ for every }p.

It follows that

\gcd(a,b)=\prod_p p^{\min(\alpha_p,\beta_p)}.

The formula works because a common divisor can contain no more copies of any prime than occur in either integer. (faculty.etsu.edu)

For instance,

72=2^3\cdot3^2,\qquad 120=2^3\cdot3\cdot5,

so their greatest common divisor is $2^3\cdot3=24$ . Taking the larger exponent of each prime instead gives their least common multiple, $2^3\cdot3^2\cdot5=360$ . These are direct applications of the exponent comparison above. (faculty.etsu.edu)

Divisors and perfect powers

For

n=p_1^{a_1}\cdots p_r^{a_r},

each positive divisor is obtained uniquely by selecting an exponent between 0 and $a_i$ for each $p_i$ . Thus the number of positive divisors is

(a_1+1)(a_2+1)\cdots(a_r+1).

Similarly, $n$ is a perfect $k$ -th power, for a positive integer $k$ , exactly when every exponent $a_i$ is divisible by $k$ . Both conclusions follow directly from uniqueness: divisors select some of the available prime factors, while raising an integer to the $k$ -th power multiplies every prime exponent by $k$ . (faculty.etsu.edu)

Rational numbers

The theorem extends to positive rational numbers by permitting negative integer exponents. Factoring the numerator and denominator yields a unique expression

q=\prod_p p^{e_p}, \qquad e_p\in\mathbb Z,

with only finitely many nonzero exponents. For example,

\frac{18}{35}=2\cdot3^2\cdot5^{-1}\cdot7^{-1}.

This is a direct consequence of applying integer prime factorization to numerator and denominator and subtracting corresponding exponents. (faculty.etsu.edu)

Generalization and limits

In abstract algebra, the integer theorem is a model for a unique factorization domain. Such a ring has no zero divisors, and every nonzero nonunit factors into irreducible elements uniquely up to order and multiplication by units. An element is irreducible if any factorization of it has a unit among its factors; a prime element satisfies the product-divisibility property used in Euclid’s lemma. These notions agree for integers but need not agree in other rings. (arxiv.org)

A standard counterexample is

\mathbb Z[\sqrt{-5}] =\{a+b\sqrt{-5}:a,b\in\mathbb Z\}.

In this ring,

6=2\cdot3=(1+\sqrt{-5})(1-\sqrt{-5}).

All four displayed factors are irreducible, yet the two factorizations cannot be made identical merely by reordering or multiplying factors by units. Unique factorization of elements therefore fails. This does not contradict the fundamental theorem of arithmetic, whose original domain is the ordinary integers. (arxiv.org)

In algebraic number theory, factorization of ideals can retain uniqueness even when factorization of elements does not. For example, every nonzero proper ideal of $\mathbb Z[\sqrt{-5}]$ has a unique factorization into prime ideals, up to order. The distinction between element factorization and ideal factorization is a central extension of the arithmetic viewpoint. (arxiv.org)

References

Fundamental Thm. of Arithmeticcourses.csail.mit.edu
Section 2. Unique Factorizationfaculty.etsu.edu
Math 79SI Notesweb.stanford.edu
MATH 417: Introduction to abstract algebra — 9/4: Unique factorisationitamar.web.illinois.edu
Euclid's Elements, Quick Tripmathcs.clarku.edu
A Historical Survey of the Fundamental Theorem of Arithmeticmath.ubc.ca
Disquisitiones arithmeticae/Sectio secundala.wikisource.org
How do elements really factor in Z[sqrt(-5)]?arxiv.org
Fundamental theorem of arithmeticen.wikipedia.org