Movatterモバイル変換

Fundamental theorem of arithmetic

From Wikipedia, the free encyclopedia

Integers have unique prime factorizations

This article is about the unique factorization of integers into prime numbers. For the theorem about roots of a polynomial, seeFundamental theorem of algebra. For other fundamental theorems, seeList of theorems called fundamental.

InDisquisitiones Arithmeticae (1801)Gauss proved the unique factorization theorem^[1] and used it to prove thelaw of quadratic reciprocity.^[2]

Inmathematics, thefundamental theorem of arithmetic, also called theunique factorization theorem andprime factorization theorem, states that everyinteger greater than 1 is either prime or can be represented uniquely as a product ofprime numbers,up to the order of the factors.^[3]^[4]^[5] For example,

1200=2^{4}\cdot 3^{1}\cdot 5^{2}=(2\cdot 2\cdot 2\cdot 2)\cdot 3\cdot (5\cdot 5)=5\cdot 2\cdot 5\cdot 2\cdot 3\cdot 2\cdot 2=\ldots

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

Using the standard conventions for theproduct of a sequence (the value of theempty product is1 and the product of a single factor is the factor itself), the theorem is often stated as:every positive integer can be represented uniquely as a product of prime numbers, up to the order of the factors.

This theorem is one of the mainreasons why 1 is not considered a prime number: if 1 were prime, then factorization into primes would not be unique; for example, $2=2\cdot 1=2\cdot 1\cdot 1=\ldots$

The theorem generalizes to otheralgebraic structures that are calledunique factorization domains and includeprincipal ideal domains,Euclidean domains, andpolynomial rings over afield. However, the theorem does not hold foralgebraic integers.^[a] This failure of unique factorization is one of the reasons for the difficulty of the proof ofFermat's Last Theorem. The implicit use of unique factorization in rings of algebraic integers is behind the error of many of the numerous false proofs that have been written during the 358 years betweenFermat's statement andWiles's proof.

History

[edit]

The fundamental theorem can be derived from Book VII, propositions 30, 31 and 32, and Book IX, proposition 14 ofEuclid'sElements.

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

— Euclid,Elements Book VII, Proposition 30

(In modern terminology: if a primep divides the productab, thenp divides eithera orb or both.) Proposition 30 is referred to asEuclid'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 byinfinite 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 anyother prime number except those originally measuring it.

— Euclid,Elements Book IX, Proposition 14

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

WhileEuclid took the first step on the way to the existence of prime factorization,Kamāl al-Dīn al-Fārisī took the final step^[c] and stated for the first time the fundamental theorem of arithmetic.^[d]

Article 16 ofGauss'sDisquisitiones Arithmeticae seems to be the first proof of the uniqueness part of the theorem.^[1]

Applications

[edit]

Canonical representation of a positive integer

[edit]

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

n=p_{1}^{n_{1}}p_{2}^{n_{2}}\cdots p_{k}^{n_{k}}=\prod _{i=1}^{k}p_{i}^{n_{i}},

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

This representation is called thecanonical representation^[6] ofn, or thestandard form^[7]^[8] ofn. For example,

999 = 3³×37,

1000 = 2³×5³,

1001 = 7×11×13.

Factorsp⁰ = 1 may be inserted without changing the value ofn (for example,1000 = 2³×3⁰×5³). In fact, any positive integer can be uniquely represented as aninfinite product taken over all the positive prime numbers, as

n=2^{n_{1}}3^{n_{2}}5^{n_{3}}7^{n_{4}}\cdots =\prod _{i=1}^{\infty }p_{i}^{n_{i}},

where a finite number of then_i are positive integers, and the others are zero.

Allowing negative exponents provides a canonical form for positiverational numbers.

Arithmetic operations

[edit]

The canonical representations of the product,greatest common divisor (GCD), andleast common multiple (LCM) of two numbersa andb can be expressed simply in terms of the canonical representations ofa andb themselves:

{\begin{alignedat}{2}a\cdot b&=2^{a_{1}+b_{1}}3^{a_{2}+b_{2}}5^{a_{3}+b_{3}}7^{a_{4}+b_{4}}\cdots &&=\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})}.\end{alignedat}}

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

[edit]

Main article:Arithmetic function

Many arithmetic functions are defined using the canonical representation. In particular, the values ofadditive andmultiplicative functions are determined by their values on the powers of prime numbers.

Proof

[edit]

The proof of uniqueness usesEuclid's lemma (Elements VII, 30): If a primedivides the product of two integers, then it must divide at least one of these integers.

Existence

[edit]

It must be shown that every integer greater than1 is either prime or a product of primes. Letn be an integer greater than1 and make theinductive assumption that every integer greater than1 and less thann is either prime or a product of primes. Ifn is prime, there is nothing more to prove. Otherwise, there are integersa andb, wheren =a b, and1 <a ≤b <n. By the inductive hypothesis,a =p₁p₂ ⋅⋅⋅p_j andb =q₁q₂ ⋅⋅⋅q_k are products of primes. But thenn =a b =p₁p₂ ⋅⋅⋅p_jq₁q₂ ⋅⋅⋅q_k is a product of primes.

Uniqueness

[edit]

Suppose, to the contrary, there is an integer that has two distinct prime factorizations. Letn be the least such integer and writen =p₁p₂ ...p_j =q₁q₂ ...q_k, where eachp_i andq_i is prime. We see thatp₁ dividesq₁q₂ ...q_k, sop₁ divides someq_i byEuclid's lemma. Without loss of generality, sayp₁ dividesq₁. Sincep₁ andq₁ are both prime, it follows thatp₁ =q₁. Returning to our factorizations ofn, we may cancel these two factors to conclude thatp₂ ...p_j =q₂ ...q_k. We now have two distinct prime factorizations of some integer strictly smaller thann, which contradicts the minimality ofn.

Uniqueness without Euclid's lemma

[edit]

The fundamental theorem of arithmetic can also be proved without using Euclid's lemma.^[9] The proof that follows is inspired by Euclid's original version of theEuclidean algorithm.

Assume that $s {\displaystyle s}$ is the smallest positive integer which is the product of prime numbers in two different ways. Incidentally, this implies that $s {\displaystyle s}$ , if it exists, must be acomposite number greater than $1 {\displaystyle 1}$ . Now, say

{\begin{aligned}s&=p_{1}p_{2}\cdots p_{m}\\&=q_{1}q_{2}\cdots q_{n}.\end{aligned}}

Every $p_{i}$ must be distinct from every $q_{j}.$ Otherwise, if say $p_{i}=q_{j},$ then there would exist some positive integer $t=s/p_{i}=s/q_{j}$ that is smaller thans and has two distinct prime factorizations. One may also suppose that $p_{1}<q_{1},$ by exchanging the two factorizations, if needed.

Setting $P=p_{2}\cdots p_{m}$ and $Q=q_{2}\cdots q_{n},$ one has $s=p_{1}P=q_{1}Q.$ Also, since $p_{1}<q_{1},$ one has $Q<P.$ It then follows that

s-p_{1}Q=(q_{1}-p_{1})Q=p_{1}(P-Q)<s.

As the positive integers less thans have been supposed to have a unique prime factorization, $p_{1}$ must occur in the factorization of either $q_{1}-p_{1}$ orQ. The latter case is impossible, asQ, being smaller thans, must have a unique prime factorization, and $p_{1}$ differs from every $q_{j}.$ The former case is also impossible, as, if $p_{1}$ is a divisor of $q_{1}-p_{1},$ it must be also a divisor of $q_{1},$ which is impossible as $p_{1}$ and $q_{1}$ 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 $1 {\displaystyle 1}$ , not factor into any prime.

Generalizations

[edit]

This sectionneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources in this section. Unsourced material may be challenged and removed.(January 2024) (Learn how and when to remove this message)

The first generalization of the theorem is found in Gauss's second monograph (1832) onbiquadratic reciprocity. This paper introduced what is now called thering ofGaussian integers, the set of allcomplex numbersa +bi wherea andb are integers. It is now denoted by $\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 (up to the order and multiplication by units).^[10]

Similarly, in 1844 while working oncubic reciprocity,Eisenstein introduced the ring $\mathbb {Z} [\omega ]$ , where ${\textstyle \omega ={\frac {-1+{\sqrt {-3}}}{2}},}$ $\omega ^{3}=1$ is a cuberoot of unity. This is the ring ofEisenstein integers, and he proved it has the six units $\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 $\mathbb {Z} [{\sqrt {-5}}]$ . In this ring one has^[11]

6=2\cdot 3=\left(1+{\sqrt {-5}}\right)\left(1-{\sqrt {-5}}\right).

Examples like this caused the notion of "prime" to be modified. In $\mathbb {Z} \left[{\sqrt {-5}}\right]$ it can be proven that if any of the factors above can be represented as a product, for example, 2 =ab, then one ofa orb 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; for example, 2 divides neither (1 + ${\sqrt {-5}}$ ) nor (1 - ${\sqrt {-5}}$ ) even though it divides their product 6. Inalgebraic number theory 2 is calledirreducible in $\mathbb {Z} \left[{\sqrt {-5}}\right]$ (only divisible by itself or a unit) but notprime in $\mathbb {Z} \left[{\sqrt {-5}}\right]$ (if it divides a product it must divide one of the factors). The mention of $\mathbb {Z} \left[{\sqrt {-5}}\right]$ is required because 2 is prime and irreducible in $\mathbb {Z} .$ Using these definitions it can be proven that in anyintegral domain a prime must be irreducible. Euclid's classical lemma can be rephrased as "in the ring of integers $\mathbb {Z}$ every irreducible is prime". This is also true in $\mathbb {Z} [i]$ and $\mathbb {Z} [\omega ],$ but not in $\mathbb {Z} [{\sqrt {-5}}].$

The rings in which factorization into irreducibles is essentially unique are calledunique factorization domains. Important examples arepolynomial rings over the integers or over afield,Euclidean domains andprincipal ideal domains.

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

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

Any commutative Möbius monoid satisfies a unique factorization theorem and thus possesses arithmetical properties similar to those of the multiplicative semigroup of positive integers. Fundamental Theorem of Arithmetic is, in fact, a special case of the unique factorization theorem in commutative Möbius monoids.

Notes

[edit]

^In aring of algebraic integers, the factorization into prime elements may be non unique, but one can recover a unique factorization if one factors intoideals.
^Weil (2007, p. 5): "Even in Euclid, we fail to find a general statement about the uniqueness of the factorization of an integer into primes; surely he may have been aware of it, but all he has is a statement (Eucl.IX.I4) about the l.c.m. of any number of given primes."
^A. Goksel Agargun and E. Mehmet Özkan."A Historical Survey of the Fundamental Theorem of Arithmetic"(PDF).Historia Mathematica: 209.One could say that Euclid takes the first step on the way to the existence of prime factorization, and al-Farisi takes the final step by actually proving the existence of a finite prime factorization in his first proposition.
^Rashed, Roshdi (2002-09-11).Encyclopedia of the History of Arabic Science. Routledge. p. 385.ISBN 9781134977246.The famous physicist and mathematician Kamal al-Din al-Farisi compiled a paper in which he set out deliberately to prove the theorem of Ibn Qurra in an algebraic way. This forced him to an understanding of the first arithmetical functions and to a full preparation which led him to state for the first time the fundamental theorem of arithmetic.

Citations

[edit]

^^a ^bGauss (1986, Art. 16)
^Gauss (1986, Art. 131)
^Long (1972, p. 44)
^Pettofrezzo & Byrkit (1970, p. 53)
^Hardy & Wright (2008, Thm 2)
^Long (1972, p. 45)
^Pettofrezzo & Byrkit (1970, p. 55)
^Hardy & Wright (2008, § 1.2)
^Dawson, John W. (2015),Why Prove it Again? Alternative Proofs in Mathematical Practice., Springer, p. 45,ISBN 9783319173689
^Gauss, BQ, §§ 31–34
^Hardy & Wright (2008, § 14.6)

References

[edit]

TheDisquisitiones 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 (1986),Disquisitiones Arithemeticae (Second, corrected edition), translated by Clarke, Arthur A., New York:Springer,ISBN 978-0-387-96254-2
Gauss, Carl Friedrich (1965),Untersuchungen über hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition) (in German), translated by Maser, H., 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 theDisquisitiones 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'sWerke, Vol II, pp. 65–92 and 93–148; German translations are pp. 511–533 and 534–586 of the German edition of theDisquisitiones.

Euclid (1956),The thirteen books of the Elements, vol. 2 (Books III-IX), Translated byThomas Little Heath (Second Edition Unabridged ed.), New York:Dover,ISBN 978-0-486-60089-5{{citation}}:ISBN / Date incompatibility (help)
Hardy, G. H.;Wright, E. M. (2008) [1938],An Introduction to the Theory of Numbers, Revised byD. R. Heath-Brown andJ. H. Silverman. Foreword byAndrew Wiles. (6th ed.), Oxford:Oxford University Press,ISBN 978-0-19-921986-5,MR 2445243,Zbl 1159.11001
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

External links

[edit]

Why isn’t the fundamental theorem of arithmetic obvious?
GCD and the Fundamental Theorem of Arithmetic atcut-the-knot.
PlanetMath: Proof of fundamental theorem of arithmetic
Fermat's Last Theorem Blog: Unique Factorization, a blog that covers the history ofFermat's Last Theorem fromDiophantus of Alexandria to the proof byAndrew Wiles.
"Fundamental Theorem of Arithmetic" by Hector Zenil,Wolfram Demonstrations Project, 2007.
Grime, James (3 February 2012),"1 and Prime Numbers",Numberphile,Brady Haran,archived from the original on 2021-12-11
Fundamental Theorem of Arithmetic

v t e Divisibility-based sets of integers
Overview	Integer factorization Divisor Unitary divisor Divisor function Prime factor Fundamental theorem of arithmetic
Factorization forms	Prime Composite Semiprime Pronic Sphenic Square-free Powerful Perfect power Achilles Smooth Regular Rough Unusual
Constrained divisor sums	Perfect Almost perfect Quasiperfect Multiply perfect Hemiperfect Hyperperfect Superperfect Unitary perfect Semiperfect Practical Descartes Erdős–Nicolas
With many divisors	Abundant Primitive abundant Highly abundant Superabundant Colossally abundant Highly composite Superior highly composite Weird
Aliquot sequence-related	Untouchable Amicable (Triple) Sociable Betrothed
Base-dependent	Equidigital Extravagant Frugal Harshad Polydivisible Smith
Other sets	Arithmetic Deficient Friendly Solitary Sublime Harmonic divisor Refactorable Superperfect