mjhjmtu

The unique factorization theorem was proved by Gauss with his 1801 book Disquisitiones Arithmeticae.^[1] In this book, Gauss used the fundamental theorem for proving the law of quadratic reciprocity.^[2]

In number theory, the fundamental theorem of arithmetic, also called the unique factorization theorem or the unique-prime-factorization theorem, states that every integer greater than 1^[3] either is a prime number itself or can be represented as the product of prime numbers and that, moreover, this representation is unique, up to (except for) the order of the factors.^[4][5][6] For example,

1200 = 2⁴ × 3¹ × 5² = 2 x 2 x 2 x 2 x 3 x 5 x 5 = 5 × 2 × 5 × 2 × 3 × 2 × 2 = ...

The theorem says two things for this example: first, that 1200 can 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 numbers may not be unique (e.g., 12 = 2 × 6 = 3 × 4).

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, 2 = 2 × 1 = 2 × 1 × 1 = ...

Euclid's original version

Book VII, propositions 30, 31 and 32, and Book IX, proposition 14 of Euclid's Elements are essentially the statement and proof of the fundamental theorem.

If two numbers by multiplying one another make some
number, and any prime number measure the product, it will
also measure one of the original numbers.

— Euclid, Elements Book VII, Proposition 30

(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, and it is the key in the proof of the fundamental theorem of arithmetic.

Any composite number is measured by some prime number.

— Euclid, Elements Book VII, Proposition 31

(In modern terminology: every integer greater than one is divided evenly by some prime number.) Proposition 31 is proved directly by infinite descent.

Any number either is prime or is measured by some prime number.

— Euclid, Elements Book VII, Proposition 32

Proposition 32 is derived from proposition 31, and proves that the decomposition is possible.

If a number be the least that is measured by prime numbers, it will not be measured by any
other prime number except those originally measuring it.

— Euclid, Elements Book IX, Proposition 14

(In modern terminology: a least common multiple 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.^[7] Indeed, in this proposition the exponents are all equal to one, so nothing is said for the general case.

Article 16 of Gauss' Disquisitiones Arithmeticae is an early modern statement and proof employing modular arithmetic.^[1]

Applications

Canonical representation of a positive integer

Every positive integer n > 1 can be represented in exactly one way as a product of prime powers:

n=p1n1p2n2⋯pknk=∏i=1kpinidisplaystyle n=p_1^n_1p_2^n_2cdots p_k^n_k=prod _i=1^kp_i^n_i

where p₁ < p₂ < ... < p_k are primes and the n_i are positive integers. This representation is commonly extended to all positive integers, including 1, by the convention that the empty product is equal to 1 (the empty product corresponds to k = 0).

This representation is called the canonical representation^[8] of n, or the standard form^[9][10] of n. For example,

999 = 3³×37,

1000 = 2³×5³,

1001 = 7×11×13.

Note that factors p⁰ = 1 may be inserted without changing the value of n (e.g., 1000 = 2³×3⁰×5³).
In fact, any positive integer can be uniquely represented as an infinite product taken over all the positive prime numbers:

n=2n13n25n37n4⋯=∏i=1∞pini,displaystyle n=2^n_13^n_25^n_37^n_4cdots =prod _i=1^infty p_i^n_i,

where a finite number of the n_i are positive integers, and the rest are zero. Allowing negative exponents provides a canonical form for positive rational numbers.

Arithmetic operations

The canonical representations of the product, greatest common divisor (GCD), and least common multiple (LCM) of two numbers a and b can be expressed simply in terms of the canonical representations of a and b themselves:

a⋅b=2a1+b13a2+b25a3+b37a4+b4⋯=∏piai+bi,gcd(a,b)=2min(a1,b1)3min(a2,b2)5min(a3,b3)7min(a4,b4)⋯=∏pimin(ai,bi),lcm⁡(a,b)=2max(a1,b1)3max(a2,b2)5max(a3,b3)7max(a4,b4)⋯=∏pimax(ai,bi).displaystyle beginalignedat2acdot b&=2^a_1+b_13^a_2+b_25^a_3+b_37^a_4+b_4cdots &&=prod p_i^a_i+b_i,\gcd(a,b)&=2^min(a_1,b_1)3^min(a_2,b_2)5^min(a_3,b_3)7^min(a_4,b_4)cdots &&=prod p_i^min(a_i,b_i),\operatorname lcm (a,b)&=2^max(a_1,b_1)3^max(a_2,b_2)5^max(a_3,b_3)7^max(a_4,b_4)cdots &&=prod p_i^max(a_i,b_i).endalignedat

However, integer factorization, 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 and multiplicative functions are determined by their values on the powers of prime numbers.

Proof

The proof uses Euclid's lemma (Elements VII, 30): if a prime p divides the product of two natural numbers a and b, then p divides a or p divides b.

Existence

We need to show that every integer greater than 1 is either prime or a product of primes.
For the base case, note that 2 is prime.
By strong induction: assume true for all numbers between 1 and n. If n is prime, there is nothing more to prove. Otherwise, there are integers a and b, where n = ab and 1 < a ≤ b < n.
By the induction hypothesis,
a = p₁p₂...p_j
and
b = q₁q₂...q_k are products of primes. But then
n = ab = p₁p₂...p_jq₁q₂...q_k is a product of primes.

Uniqueness

Assume that s > 1 is the product of prime numbers in two different ways:

s=p1p2⋯pm=q1q2⋯qn.displaystyle beginaligneds&=p_1p_2cdots p_m\&=q_1q_2cdots q_n.endaligned

We must show m = n and that the q_j are a rearrangement of the p_i.

As p₁ divides s, Euclid's lemma implies that p₁ divides one of the q_j; relabeling the q_j if necessary, say that p₁ divides q₁. But q₁ is prime, so its only divisors are itself and 1. Therefore, p₁ = q₁, so that

sp1=p2⋯pm=q2⋯qn.displaystyle beginalignedfrac sp_1&=p_2cdots p_m\&=q_2cdots q_n.endaligned

Reasoning the same way, p₂ must equal one of the remaining q_j. Relabeling again if necessary, say p₂ = q₂. Then

sp1p2=p3⋯pm=q3⋯qn.displaystyle beginalignedfrac sp_1p_2&=p_3cdots p_m\&=q_3cdots q_n.endaligned

This can be done for each of the m p_i's, showing that m ≤ n and every p_i is a q_j. Applying the same argument with the pdisplaystyle p's and qdisplaystyle q's reversed shows n ≤ m (hence m = n) and every q_j is a p_i.

Elementary proof of uniqueness

The fundamental theorem of arithmetic can also be proved without using Euclid's lemma, as follows:

Assume that s > 1 is the smallest positive integer which is the product of prime numbers in two different ways. If s were prime then it would factor uniquely as itself, so there must be at least two primes in each factorization of s:

s=p1p2⋯pm=q1q2⋯qn.displaystyle beginaligneds&=p_1p_2cdots p_m\&=q_1q_2cdots q_n.endaligned

If any p_i = q_j then, by cancellation, s/p_i = s/q_j would be another positive integer, different from s, which is greater than 1 and also has two distinct factorizations. But s/p_i is smaller than s, meaning s would not actually be the smallest such integer. Therefore every p_i must be distinct from every q_j.

Without loss of generality, take p₁ < q₁ (if this is not already the case, switch the p and q designations.) Consider

t=(q1−p1)(q2⋯qn),displaystyle t=(q_1-p_1)(q_2cdots q_n),

and note that 1 < q₂ ≤ t < s. Therefore t must have a unique prime factorization. By rearrangement we see,

t=q1(q2⋯qn)−p1(q2⋯qn)=s−p1(q2⋯qn)=p1((p2⋯pm)−(q2⋯qn)).displaystyle beginalignedt&=q_1(q_2cdots q_n)-p_1(q_2cdots q_n)\&=s-p_1(q_2cdots q_n)\&=p_1((p_2cdots p_m)-(q_2cdots q_n)).endaligned

Here u = ((p₂ ... p_m) - (q₂ ... q_n)) is positive, for if it were negative or zero then so would be its product with p₁, but that product equals t which is positive. So u is either 1 or factors into primes. In either case, t = p₁u yields a prime factorization of t, which we know to be unique, so p₁ appears in the prime factorization of t.

If (q₁ - p₁) equaled 1 then the prime factorization of t would be all q's, which would preclude p₁ from appearing. Thus (q₁ - p₁) is not 1, but is positive, so it factors into primes: (q₁ - p₁) = (r₁ ... r_h). This yields a prime factorization of

t=(r1⋯rh)(q2⋯qn),displaystyle t=(r_1cdots r_h)(q_2cdots q_n),

which we know is unique. Now, p₁ appears in the prime factorization of t, and it is not equal to any q, so it must be one of the r's. That means p₁ is a factor of (q₁ - p₁), so there exists a positive integer k such that p₁k = (q₁ - p₁), and therefore

p1(k+1)=q1.displaystyle p_1(k+1)=q_1.

But that means q₁ has a proper factorization, so it is not a prime number. This contradiction shows that s does not actually have two different prime factorizations. As a result, there is no smallest positive integer with multiple prime factorizations, hence all positive integers greater than 1 factor uniquely into primes.

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 of Gaussian integers, the set of all complex numbers a + bi where a and b are integers. It is now denoted by Z[i].displaystyle mathbb Z [i]. 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.^[11]

Similarly, in 1844 while working on cubic reciprocity, Eisenstein introduced the ring Z[ω]displaystyle mathbb Z [omega ], where ω=−1+−32,displaystyle omega =frac -1+sqrt -32,   ω3=1displaystyle omega ^3=1 is a cube root of unity. This is the ring of Eisenstein integers, and he proved it has the six units ±1,±ω,±ω2displaystyle pm 1,pm omega ,pm omega ^2 and that it has unique factorization.

However, it was also discovered that unique factorization does not always hold. An example is given by Z[−5]displaystyle mathbb Z [sqrt -5]. In this ring one has^[12]

6=2⋅3=(1+−5)(1−−5).displaystyle 6=2cdot 3=(1+sqrt -5)(1-sqrt -5).

Examples like this caused the notion of "prime" to be modified. In Z[−5]displaystyle mathbb Z [sqrt -5] it can be proven that if any of the factors above can be represented as a product, e.g., 2 = ab, then one of a or b must be a unit. This is the traditional definition of "prime". It can also be proven that none of these factors obeys Euclid's lemma; e.g.,
2 divides neither (1 + √−5) nor (1 − √−5) even though it divides their product 6. In algebraic number theory 2 is called irreducible in Z[−5]displaystyle mathbb Z [sqrt -5] (only divisible by itself or a unit) but not prime in Z[−5]displaystyle mathbb Z [sqrt -5] (if it divides a product it must divide one of the factors). The mention of Z[−5]displaystyle mathbb Z [sqrt -5] is required because 2 is prime and irreducible in Z.displaystyle mathbb Z . Using these definitions it can be proven that in any ring a prime must be irreducible. Euclid's classical lemma can be rephrased as "in the ring of integers Zdisplaystyle mathbb Z every irreducible is prime". This is also true in Z[i]displaystyle mathbb Z [i] and Z[ω],displaystyle mathbb Z [omega ], but not in Z[−5].displaystyle mathbb Z [sqrt -5].

The rings in which factorization into irreducibles is essentially unique are called unique factorization domains. Important examples are polynomial rings over the integers or over a field, Euclidean domains and principal ideal domains.

In 1843 Kummer introduced the concept of ideal number, which was developed further by Dedekind (1876) into the modern theory of ideals, special subsets of rings. Multiplication is defined for ideals, and the rings in which they have unique factorization are called Dedekind domains.

There is a version of unique factorization for ordinals, though it requires some additional conditions to ensure uniqueness.

See also

• Euler product formula


• Integer factorization


• Noetherian ring


• Prime signature

Notes

References

The Disquisitiones Arithmeticae has been translated from Latin into English and German. The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes.

• 
  Gauss, Carl Friedrich; Clarke, Arthur A. (translator into English) (1986), Disquisitiones Arithemeticae (Second, corrected edition), New York: Springer, ISBN 978-0-387-96254-2.mw-parser-output cite.citationfont-style:inherit.mw-parser-output .citation qquotes:"""""""'""'".mw-parser-output .citation .cs1-lock-free abackground:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration abackground:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center.mw-parser-output .citation .cs1-lock-subscription abackground:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registrationcolor:#555.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration spanborder-bottom:1px dotted;cursor:help.mw-parser-output .cs1-ws-icon abackground:url("//upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Wikisource-logo.svg/12px-Wikisource-logo.svg.png")no-repeat;background-position:right .1em center.mw-parser-output code.cs1-codecolor:inherit;background:inherit;border:inherit;padding:inherit.mw-parser-output .cs1-hidden-errordisplay:none;font-size:100%.mw-parser-output .cs1-visible-errorfont-size:100%.mw-parser-output .cs1-maintdisplay:none;color:#33aa33;margin-left:0.3em.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-formatfont-size:95%.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-leftpadding-left:0.2em.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-rightpadding-right:0.2em
  


• 
  Gauss, Carl Friedrich; Maser, H. (translator into German) (1965), Untersuchungen über hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition), New York: Chelsea, ISBN 0-8284-0191-8
  

The two monographs Gauss published on biquadratic reciprocity have consecutively numbered sections: the first contains §§ 1–23 and the second §§ 24–76. Footnotes referencing these are of the form "Gauss, BQ, § n". Footnotes referencing the Disquisitiones Arithmeticae are of the form "Gauss, DA, Art. n".

• 
  Gauss, Carl Friedrich (1828), Theoria residuorum biquadraticorum, Commentatio prima, Göttingen: Comment. Soc. regiae sci, Göttingen 6
  


• 
  Gauss, Carl Friedrich (1832), Theoria residuorum biquadraticorum, Commentatio secunda, Göttingen: Comment. Soc. regiae sci, Göttingen 7
  

These are in Gauss's Werke, Vol II, pp. 65–92 and 93–148; German translations are pp. 511–533 and 534–586 of the German edition of the Disquisitiones.

• 
  Baker, Alan (1984), A Concise Introduction to the Theory of Numbers, Cambridge, UK: Cambridge University Press, ISBN 978-0-521-28654-1
  


• 
  Euclid (1956), The thirteen books of the Elements, 2 (Books III-IX), Translated by Thomas Little Heath (Second Edition Unabridged ed.), New York: Dover, ISBN 978-0-486-60089-5
  


• 
  Hardy, G. H.; Wright, E. M. (2008) [1938]. An Introduction to the Theory of Numbers. Revised by D. R. Heath-Brown and J. H. Silverman. Foreword by Andrew Wiles. (6th ed.). Oxford: Oxford University Press. ISBN 978-0-19-921986-5. MR 2445243. Zbl 1159.11001.
  


• 
  A. Kornilowicz; P. Rudnicki (2004), "Fundamental theorem of arithmetic", Formalized Mathematics, 12 (2): 179–185
  


• 
  Long, Calvin T. (1972), Elementary Introduction to Number Theory (2nd ed.), Lexington: D. C. Heath and Company, LCCN 77-171950.


• 
  Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elements of Number Theory, Englewood Cliffs: Prentice Hall, LCCN 77-81766.


• 
  Riesel, Hans (1994), Prime Numbers and Computer Methods for Factorization (second edition), Boston: Birkhäuser, ISBN 0-8176-3743-5
  


• 
  Weil, André (2007) [1984]. Number Theory: An Approach through History from Hammurapi to Legendre. Modern Birkhäuser Classics. Boston, MA: Birkhäuser. ISBN 978-0-817-64565-6.
  


• Weisstein, Eric W. "Abnormal number". MathWorld.


• Weisstein, Eric W. "Fundamental Theorem of Arithmetic". MathWorld.

External links

• Why isn’t the fundamental theorem of arithmetic obvious?


• 
  GCD and the Fundamental Theorem of Arithmetic at cut-the-knot.


• PlanetMath: Proof of fundamental theorem of arithmetic


• 
  Fermat's Last Theorem Blog: Unique Factorization, a blog that covers the history of Fermat's Last Theorem from Diophantus of Alexandria to the proof by Andrew Wiles.


• 
  "Fundamental Theorem of Arithmetic" by Hector Zenil, Wolfram Demonstrations Project, 2007.


• 
  Grime, James. "1 and Prime Numbers". Numberphile. Brady Haran.