In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the fundamental theorem of arithmetic, also called the unique factorization theorem and prime factorization theorem, states that every
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
greater than 1 can be represented uniquely as a product of
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s,
up to Two Mathematical object, mathematical objects ''a'' and ''b'' are called equal up to an equivalence relation ''R''
* if ''a'' and ''b'' are related by ''R'', that is,
* if ''aRb'' holds, that is,
* if the equivalence classes of ''a'' and ''b'' wi ...
the order of the factors. For example,
:
The theorem says two things about this example: first, that 1200 be represented as a product of primes, and second, that no matter how this is done, there will always be exactly four 2s, one 3, two 5s, and no other primes in the product.
The requirement that the factors be prime is necessary: factorizations containing
composite number
A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime, ...
s may not be unique
(for example,
).
This theorem is one of the main
reasons why 1 is not considered a prime number: if 1 were prime, then factorization into primes would not be unique; for example,
This theorem generalizes to other
algebraic structure
In mathematics, an algebraic structure consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplication), and a finite set of ...
s, in particular to
polynomial ring
In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring (which is also a commutative algebra) formed from the set of polynomials in one or more indeterminates (traditionally also called variables) ...
s over a
field
Field may refer to:
Expanses of open ground
* Field (agriculture), an area of land used for agricultural purposes
* Airfield, an aerodrome that lacks the infrastructure of an airport
* Battlefield
* Lawn, an area of mowed grass
* Meadow, a grass ...
. These structures are called
unique factorization domain
In mathematics, a unique factorization domain (UFD) (also sometimes called a factorial ring following the terminology of Bourbaki) is a ring in which a statement analogous to the fundamental theorem of arithmetic holds. Specifically, a UFD is an ...
s.
Euclid's original version
Book VII, propositions 30, 31 and 32, and Book IX, proposition 14 of
Euclid
Euclid (; grc-gre, Wikt:Εὐκλείδης, Εὐκλείδης; BC) was an ancient Greek mathematician active as a geometer and logician. Considered the "father of geometry", he is chiefly known for the ''Euclid's Elements, Elements'' trea ...
's ''
Elements'' are essentially the statement and proof of the fundamental theorem.
(In modern terminology: if a prime ''p'' divides the product ''ab'', then ''p'' divides either ''a'' or ''b'' or both.) Proposition 30 is referred to as
Euclid's lemma
In algebra and number theory, Euclid's lemma is a lemma that captures a fundamental property of prime numbers, namely:
For example, if , , , then , and since this is divisible by 19, the lemma implies that one or both of 133 or 143 must be as w ...
, and it is the key in the proof of the fundamental theorem of arithmetic.
(In modern terminology: every integer greater than one is divided evenly by some prime number.) Proposition 31 is proved directly by
infinite descent In mathematics, a proof by infinite descent, also known as Fermat's method of descent, is a particular kind of proof by contradiction used to show that a statement cannot possibly hold for any number, by showing that if the statement were to hold f ...
.
Proposition 32 is derived from proposition 31, and proves that the decomposition is possible.
(In modern terminology: a
least common multiple
In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers ''a'' and ''b'', usually denoted by lcm(''a'', ''b''), is the smallest positive integer that is divisible by bo ...
of several prime numbers is not a multiple of any other prime number.) Book IX, proposition 14 is derived from Book VII, proposition 30, and proves partially that the decomposition is unique – a point critically noted by
André Weil. Indeed, in this proposition the exponents are all equal to one, so nothing is said for the general case.
Article 16 of
Gauss
Johann Carl Friedrich Gauss (; german: Gauß ; la, Carolus Fridericus Gauss; 30 April 177723 February 1855) was a German mathematician and physicist who made significant contributions to many fields in mathematics and science. Sometimes refer ...
' ''
Disquisitiones Arithmeticae
The (Latin for "Arithmetical Investigations") is a textbook of number theory written in Latin by Carl Friedrich Gauss in 1798 when Gauss was 21 and first published in 1801 when he was 24. It is notable for having had a revolutionary impact on th ...
'' is an early modern statement and proof employing
modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book ...
.
Applications
Canonical representation of a positive integer
Every positive integer can be represented in exactly one way as a product of prime powers
:
where are primes and the are positive integers. This representation is commonly extended to all positive integers, including 1, by the convention that the
empty product
In mathematics, an empty product, or nullary product or vacuous product, is the result of multiplying no factors. It is by convention equal to the multiplicative identity (assuming there is an identity for the multiplication operation in question ...
is equal to 1 (the empty product corresponds to ).
This representation is called the canonical representation of , or the standard form of ''n''. For example,
:999 = 3
3×37,
:1000 = 2
3×5
3,
:1001 = 7×11×13.
Factors may be inserted without changing the value of (for example, ). In fact, any positive integer can be uniquely represented as an
infinite product In mathematics, for a sequence of complex numbers ''a''1, ''a''2, ''a''3, ... the infinite product
:
\prod_^ a_n = a_1 a_2 a_3 \cdots
is defined to be the limit of the partial products ''a''1''a''2...''a'n'' as ''n'' increases without bound. ...
taken over all the positive prime numbers, as
:
where a finite number of the are positive integers, and the others are zero.
Allowing negative exponents provides a canonical form for positive
rational number
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ration ...
s.
Arithmetic operations
The canonical representations of the product,
greatest common divisor
In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...
(GCD), and
least common multiple
In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers ''a'' and ''b'', usually denoted by lcm(''a'', ''b''), is the smallest positive integer that is divisible by bo ...
(LCM) of two numbers ''a'' and ''b'' can be expressed simply in terms of the canonical representations of ''a'' and ''b'' themselves:
:
However,
integer factorization
In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization.
When the numbers are suf ...
, especially of large numbers, is much more difficult than computing products, GCDs, or LCMs. So these formulas have limited use in practice.
Arithmetic functions
Many arithmetic functions are defined using the canonical representation. In particular, the values of
additive
Additive may refer to:
Mathematics
* Additive function, a function in number theory
* Additive map, a function that preserves the addition operation
* Additive set-functionn see Sigma additivity
* Additive category, a preadditive category with f ...
and
multiplicative functions are determined by their values on the powers of prime numbers.
Proof
The proof uses
Euclid's lemma
In algebra and number theory, Euclid's lemma is a lemma that captures a fundamental property of prime numbers, namely:
For example, if , , , then , and since this is divisible by 19, the lemma implies that one or both of 133 or 143 must be as w ...
(''Elements'' VII, 30): If a prime
divides
In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...
the product of two integers, then it must divide at least one of these integers.
Existence
It must be shown that every integer greater than is either prime or a product of primes. First, is prime. Then, by
strong induction
Mathematical induction is a method for proving that a statement ''P''(''n'') is true for every natural number ''n'', that is, that the infinitely many cases ''P''(0), ''P''(1), ''P''(2), ''P''(3), ... all hold. Informal metaphors help ...
, assume this is true for all numbers greater than and less than . If is prime, there is nothing more to prove. Otherwise, there are integers and , where , and . By the induction hypothesis, and are products of primes. But then is a product of primes.
Uniqueness
Suppose, to the contrary, there is an integer that has two distinct prime factorizations. Let be the least such integer and write , where each and is prime. We see that divides , so divides some by
Euclid's lemma
In algebra and number theory, Euclid's lemma is a lemma that captures a fundamental property of prime numbers, namely:
For example, if , , , then , and since this is divisible by 19, the lemma implies that one or both of 133 or 143 must be as w ...
. Without loss of generality, say divides . Since and are both prime, it follows that . Returning to our factorizations of , we may cancel these two factors to conclude that . We now have two distinct prime factorizations of some integer strictly smaller than , which contradicts the minimality of .
Uniqueness without Euclid's lemma
The fundamental theorem of arithmetic can also be proved without using Euclid's lemma. The proof that follows is inspired by Euclid's original version of the
Euclidean algorithm
In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is an effi ...
.
Assume that
is the smallest positive integer which is the product of prime numbers in two different ways. Incidentally, this implies that
, if it exists, must be a
composite number
A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime, ...
greater than
. Now, say
:
Every
must be distinct from every
Otherwise, if say
then there would exist some positive integer
that is smaller than and has two distinct prime factorizations. One may also suppose that
by exchanging the two factorizations, if needed.
Setting
and
one has
Also, since
one has
It then follows that
:
As the positive integers less than have been supposed to have a unique prime factorization,
must occur in the factorization of either
or . The latter case is impossible, as , being smaller than , must have a unique prime factorization, and
differs from every
The former case is also impossible, as, if
is a divisor of
it must be also a divisor of
which is impossible as
and
are distinct primes.
Therefore, there cannot exist a smallest integer with more than a single distinct prime factorization. Every positive integer must either be a prime number itself, which would factor uniquely, or a composite that also factors uniquely into primes, or in the case of the integer
, not factor into any prime.
Generalizations
The first generalization of the theorem is found in Gauss's second monograph (1832) on
biquadratic reciprocity. This paper introduced what is now called the
ring
Ring may refer to:
* Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry
* To make a sound with a bell, and the sound made by a bell
:(hence) to initiate a telephone connection
Arts, entertainment and media Film and ...
of
Gaussian integer
In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as \mathbf /ma ...
s, the set of all
complex number
In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the form ...
s ''a'' + ''bi'' where ''a'' and ''b'' are integers. It is now denoted by
He showed that this ring has the four units ±1 and ±''i'', that the non-zero, non-unit numbers fall into two classes, primes and composites, and that (except for order), the composites have unique factorization as a product of primes.
Similarly, in 1844 while working on
cubic reciprocity
Cubic reciprocity is a collection of theorems in elementary and algebraic number theory that state conditions under which the congruence ''x''3 ≡ ''p'' (mod ''q'') is solvable; the word "reciprocity" comes from the form of ...
,
Eisenstein introduced the ring