Old page wikitext, before the edit (old_wikitext) | '{{short description|A positive integer factorizes uniquely into a product of primes}}
{{Distinguish|Fundamental theorem of algebra}}
[[File:Disqvisitiones-800.jpg|thumb|The unique factorization theorem was proved by [[Carl Friedrich Gauss|Gauss]] with his 1801 book ''[[Disquisitiones Arithmeticae]]''.<ref name="Gauss1801.loc=16">{{Harvtxt|Gauss|Clarke|1986|loc=Art. 16}}</ref> In this book, Gauss used the fundamental theorem for proving the [[law of quadratic reciprocity]].<ref>{{Harvtxt|Gauss|Clarke|1986|loc=Art. 131}}</ref>]]
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<ref>Using the [[empty product|empty product rule]] one need not exclude the number 1, and the theorem can be stated as: every positive integer has unique prime factorization.</ref> 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.<ref>{{harvtxt|Long|1972|p=44}}</ref><ref>{{harvtxt|Pettofrezzo|Byrkit|1970|p=53}}</ref><ref>{{Harvtxt|Hardy|Wright|2008|loc=Thm 2}}</ref> For example,
:1200 = 2{{sup|4}} × 3{{sup|1}} × 5{{sup|2}} = 2 × 2 × 2 × 2 × 3 × 5 × 5 = 5 × 2 × 5 × 2 × 3 × 2 × 2 = ...
The theorem says two things for this example: first, that 1200 {{em|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 number]]s may not be unique (e.g., 12 = 2 × 6 = 3 × 4).
This theorem is one of the main [[Prime number#Primality of one|reasons why 1 is not considered a prime number]]: if 1 were prime, then factorization into primes would not be unique; for example, {{nowrap|1=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 ''[[Euclid's Elements|Elements]]'' are essentially the statement and proof of the fundamental theorem.
{{Quotation|
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|[[#CITEREFEuclidHeath1956|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.
{{Quotation|
Any composite number is measured by some prime number.
|Euclid|[[#CITEREFEuclidHeath1956|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 [[Proof by infinite descent|infinite descent]].
{{Quotation|
Any number either is prime or is measured by some prime number.
|Euclid|[[#CITEREFEuclidHeath1956|Elements Book VII]], Proposition 32}}
Proposition 32 is derived from proposition 31, and proves that the decomposition is possible.
{{Quotation|
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|[[#CITEREFEuclidHeath1956|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]].<ref>{{Harvtxt|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."</ref> Indeed, in this proposition the exponents are all equal to one, so nothing is said for the general case.
Article 16 of [[Carl Friedrich Gauss|Gauss]]' ''[[Disquisitiones Arithmeticae]]'' is an early modern statement and proof employing [[modular arithmetic]].<ref name="Gauss1801.loc=16" />
==Applications==
===Canonical representation of a positive integer=== <!-- Redirect [[Canonical form]] links here -->
Every positive integer ''n'' > 1 can be represented in exactly one way as a product of prime powers:
:<math>
n = p_1^{n_1}p_2^{n_2} \cdots p_k^{n_k}
= \prod_{i=1}^{k} p_i^{n_i}
</math>
where {{nowrap begin}}''p''<sub>1</sub> < ''p''<sub>2</sub> < ... < ''p''<sub>k</sub>{{nowrap end}} are primes and the ''n''<sub>''i''</sub> 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'''<ref>{{harvtxt|Long|1972|p=45}}</ref> of ''n'', or the '''standard form'''<ref>{{harvtxt|Pettofrezzo|Byrkit|1970|p=55}}</ref><ref>{{Harvtxt|Hardy|Wright|2008|loc=§ 1.2}}</ref> of ''n''. For example,
:999 = 3<sup>3</sup>×37,
:1000 = 2<sup>3</sup>×5<sup>3</sup>,
:1001 = 7×11×13.
Note that factors ''p''<sup>0</sup> = 1 may be inserted without changing the value of ''n'' (e.g., 1000 = 2<sup>3</sup>×3<sup>0</sup>×5<sup>3</sup>).<br>In fact, any positive integer can be uniquely represented as an [[infinite product]] taken over all the positive prime numbers:
:<math>
n=2^{n_1}3^{n_2}5^{n_3}7^{n_4}\cdots=\prod_{i=1}^\infty p_i^{n_i},
</math>
where a finite number of the ''n''<sub>''i''</sub> are positive integers, and the rest are zero. Allowing negative exponents provides a canonical form for positive [[rational number]]s.
===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:
:<math>\begin{alignat}{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{alignat}</math>
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===
{{Main article|Arithmetic function}}
Many arithmetic functions are defined using the canonical representation. In particular, the values of [[additive function|additive]] and [[multiplicative function|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'' [[Divisor|divides]] the product of two [[natural number]]s ''a'' and ''b'', then ''p'' divides ''a'' or ''p'' divides ''b''.
===Existence===
It must be shown that every integer greater than 1 is either prime or a product of primes. First, 2 is prime. Then, by [[strong induction]], assume this is true for all numbers greater than 1 and less than ''n''. If ''n'' is prime, there is nothing more to prove. Otherwise, there are integers ''a'' and ''b'', where ''n'' = ''ab'', and {{nowrap|1 < ''a'' ≤ ''b'' < ''n''}}. By the induction hypothesis, {{nowrap|1=''a'' = ''p''<sub>1</sub>''p''<sub>2</sub>...''p''<sub>''j''</sub>}} and {{nowrap|1=''b'' = ''q''<sub>1</sub>''q''<sub>2</sub>...''q''<sub>''k''</sub>}} are products of primes. But then {{nowrap|1=''n'' = ''ab'' = ''p''<sub>1</sub>''p''<sub>2</sub>...''p''<sub>''j''</sub>''q''<sub>1</sub>''q''<sub>2</sub>...''q''<sub>''k''</sub>}} is a product of primes.
===Uniqueness===
Suppose, to the contrary, there is an integer that has two distinct prime factorizations. Let ''n'' be the least such integer and write ''n'' = ''p''<sub>1</sub> ''p''<sub>2</sub> ... ''p''<sub>''j''</sub> = ''q''<sub>1</sub> ''q''<sub>2</sub> ... ''q''<sub>''k''</sub>, where each ''p''<sub>''i''</sub> and ''q''<sub>''i''</sub> is prime. (Note ''j'' and ''k'' are both at least 2.) We see ''p''<sub>1</sub> divides ''q''<sub>1</sub> ''q''<sub>2</sub> ... ''q''<sub>''k''</sub>, so ''p''<sub>1</sub> divides some ''q''<sub>''i''</sub> by Euclid's lemma. Without loss of generality, say ''p''<sub>1</sub> divides ''q''<sub>1</sub>. Since ''p''<sub>1</sub> and ''q''<sub>1</sub> are both prime, it follows that ''p''<sub>1</sub> = ''q''<sub>1</sub>. Returning to our factorizations of ''n'', we may cancel these two terms to conclude ''p''<sub>2</sub> ... ''p''<sub>''j''</sub> = ''q''<sub>2</sub> ... ''q''<sub>''k''</sub>. We now have two distinct prime factorizations of some integer strictly smaller than ''n'', which contradicts the minimality of ''n''.
===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'':
:<math>
\begin{align}
s
&=p_1 p_2 \cdots p_m \\
&=q_1 q_2 \cdots q_n.
\end{align}
</math>
If any ''p''<sub>''i''</sub> = ''q''<sub>''j''</sub> then, by cancellation, ''s''/''p''<sub>''i''</sub> = ''s''/''q''<sub>''j''</sub> would be another positive integer, different from s, which is greater than 1 and also has two distinct factorizations. But ''s''/''p''<sub>''i''</sub> is smaller than ''s'', meaning ''s'' would not actually be the smallest such integer. Therefore every ''p''<sub>''i''</sub> must be distinct from every ''q''<sub>''j''</sub>.
Without loss of generality, take ''p''<sub>1</sub> < ''q''<sub>1</sub> (if this is not already the case, switch the ''p'' and ''q'' designations.) Consider
:<math>t = (q_1 - p_1)(q_2 \cdots q_n),</math>
and note that 1 < ''q''<sub>2</sub> ≤ ''t'' < ''s''. Therefore ''t'' must have a unique prime factorization. By rearrangement we see,
:<math>
\begin{align}
t
&= q_1(q_2 \cdots q_n) - p_1(q_2 \cdots q_n) \\
&= s - p_1(q_2 \cdots q_n) \\
&= p_1((p_2 \cdots p_m) - (q_2 \cdots q_n)).
\end{align}
</math>
Here ''u'' = ((''p''<sub>2</sub> ... ''p''<sub>''m''</sub>) - (''q''<sub>2</sub> ... ''q''<sub>''n''</sub>)) is positive, for if it were negative or zero then so would be its product with ''p''<sub>''1''</sub>, but that product equals ''t'' which is positive. So ''u'' is either 1 or factors into primes. In either case, ''t'' = ''p''<sub>1</sub>''u'' yields a prime factorization of ''t'', which we know to be unique, so ''p''<sub>1</sub> appears in the prime factorization of ''t''.
If (''q''<sub>1</sub> - ''p''<sub>1</sub>) equaled 1 then the prime factorization of ''t'' would be all ''q'''s, which would preclude ''p''<sub>1</sub> from appearing. Thus (''q''<sub>1</sub> - ''p''<sub>1</sub>) is not 1, but is positive, so it factors into primes: (''q''<sub>1</sub> - ''p''<sub>1</sub>) = (''r''<sub>1</sub> ... ''r''<sub>''h''</sub>). This yields a prime factorization of
:<math>t = (r_1 \cdots r_h)(q_2 \cdots q_n),</math>
which we know is unique. Now, ''p''<sub>1</sub> 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''<sub>1</sub> is a factor of (''q''<sub>1</sub> - ''p''<sub>1</sub>), so there exists a positive integer ''k'' such that ''p''<sub>1</sub>''k'' = (''q''<sub>1</sub> - ''p''<sub>1</sub>), and therefore
:<math>p_1(k+1) = q_1.</math>
But that means ''q''<sub>1</sub> 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 theory|ring]] of [[Gaussian integer]]s, the set of all [[complex number]]s ''a'' + ''bi'' where ''a'' and ''b'' are integers. It is now denoted by <math>\mathbb{Z}[i].</math> 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.<ref>[[#CITEREFGauss1832|Gauss, BQ, §§ 31–34]]</ref>
Similarly, in 1844 while working on [[cubic reciprocity]], [[Gotthold Eisenstein|Eisenstein]] introduced the ring <math>\mathbb{Z}[\omega]</math>, where <math>\omega=\frac{-1+\sqrt{-3}}{2}, </math> <math>\omega^3=1 </math> is a cube [[root of unity]]. This is the ring of [[Eisenstein integer]]s, and he proved it has the six units <math>\pm 1, \pm\omega, \pm\omega^2</math> and that it has unique factorization.
However, it was also discovered that unique factorization does not always hold. An example is given by <math>\mathbb{Z}[\sqrt{-5}]</math>. In this ring one has<ref>{{Harvtxt|Hardy|Wright|2008|loc=§ 14.6}}</ref>
:<math>
6=
2\cdot 3=
(1+\sqrt{-5})(1-\sqrt{-5}).
</math>
Examples like this caused the notion of "prime" to be modified. In <math>\mathbb{Z}[\sqrt{-5}]</math> 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 + {{sqrt|−5}}) nor (1 − {{sqrt|−5}}) even though it divides their product 6. In [[algebraic number theory]] 2 is called [[irreducible element|irreducible]] in <math>\mathbb{Z}[\sqrt{-5}]</math> (only divisible by itself or a unit) but not [[prime element|prime]] in <math>\mathbb{Z}[\sqrt{-5}]</math> (if it divides a product it must divide one of the factors). The mention of <math>\mathbb{Z}[\sqrt{-5}]</math> is required because 2 is prime and irreducible in <math>\mathbb{Z}.</math> Using these definitions it can be proven that in any [[integral domain]] a prime must be irreducible. Euclid's classical lemma can be rephrased as "in the ring of integers <math>\mathbb{Z}</math> every irreducible is prime". This is also true in <math>\mathbb{Z}[i]</math> and <math>\mathbb{Z}[\omega],</math> but not in <math>\mathbb{Z}[\sqrt{-5}].</math>
The rings in which factorization into irreducibles is essentially unique are called [[unique factorization domain]]s. Important examples are [[polynomial ring]]s over the integers or over a [[field (mathematics)|field]], [[Euclidean domain]]s and [[principal ideal domain]]s.
In 1843 [[Ernst Kummer|Kummer]] introduced the concept of [[ideal number]], which was developed further by [[Richard Dedekind|Dedekind]] (1876) into the modern theory of [[Ideal (ring theory)|ideals]], special subsets of rings. Multiplication is defined for ideals, and the rings in which they have unique factorization are called [[Dedekind domain]]s.
There is a version of [[ordinal arithmetic|unique factorization for ordinals]], though it requires some additional conditions to ensure uniqueness.
==See also==
* [[Riemann zeta function#Euler product formula|Euler product formula]]
* [[Integer factorization]]
* [[Noetherian ring]]
* [[Prime signature]]
==Notes==
{{reflist|30em}}
==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.
* {{citation
| last1 = Gauss | first1 = Carl Friedrich
| last2 = Clarke | first2 = Arthur A. (translator into English)
| title = Disquisitiones Arithemeticae (Second, corrected edition)
| publisher = [[Springer Science+Business Media|Springer]]
| location = New York
| year = 1986
| isbn = 978-0-387-96254-2
| url = https://www.springer.com/mathematics/algebra/book/978-0-387-96254-2
}}
* {{citation
| last1 = Gauss | first1 = Carl Friedrich
| last2 = Maser | first2 = H. (translator into German)
| title = Untersuchungen über hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition)
| publisher = Chelsea
| location = New York
| year = 1965
| 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''".
* {{citation
| last1 = Gauss | first1 = Carl Friedrich
| title = Theoria residuorum biquadraticorum, Commentatio prima
| publisher = Comment. Soc. regiae sci, Göttingen 6
| location = Göttingen
| year = 1828}}
* {{citation
| last1 = Gauss | first1 = Carl Friedrich
| title = Theoria residuorum biquadraticorum, Commentatio secunda
| publisher = Comment. Soc. regiae sci, Göttingen 7
| location = Göttingen
| year = 1832}}
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''.
* {{Citation
| last=Baker
| first=Alan
| author-link=
| year=1984
| title=A Concise Introduction to the Theory of Numbers
| place=Cambridge, UK
| publisher=Cambridge University Press
| isbn=978-0-521-28654-1
}}
* {{citation
| author1 = Euclid
| author1-link = Euclid
| others = Translated by [[Thomas Little Heath]]
| title = The thirteen books of the Elements
| edition = Second Edition Unabridged
| volume = 2 (Books III-IX)
| publisher = [[Dover]]
| location = New York
| year = 1956
| isbn = 978-0-486-60089-5
| url = http://store.doverpublications.com/0486600890.html
}}
* {{Hardy and Wright}}
* {{Citation
| author1 = A. Kornilowicz
| author2 = P. Rudnicki
| year = 2004
| title = Fundamental theorem of arithmetic
| journal = [[Formalized Mathematics]]
| volume = 12
| issue = 2
| pages = 179–185
}}
* {{citation
| first1 = Calvin T.
| last1 = Long
| year = 1972
| title = Elementary Introduction to Number Theory
| edition = 2nd | publisher = [[D. C. Heath and Company]]
| location = Lexington
| lccn = 77-171950
}}.
* {{citation
| first1 = Anthony J.
| last1 = Pettofrezzo
| first2 = Donald R.
| last2 = Byrkit
| year = 1970
| title = Elements of Number Theory
| publisher = [[Prentice Hall]]
| location = Englewood Cliffs
| lccn = 77-81766
}}.
* {{citation
| last1 = Riesel | first1 = Hans
| title = Prime Numbers and Computer Methods for Factorization (second edition)
| publisher = Birkhäuser
| location = Boston
| year = 1994
| isbn = 0-8176-3743-5}}
* {{Cite book |last= Weil |first= André |year= 2007 |origyear= 1984 |title= [[Number Theory: An Approach through History from Hammurapi to Legendre]] |series= Modern Birkhäuser Classics |location= Boston, MA |publisher= Birkhäuser |isbn= 978-0-817-64565-6 |ref= harv }}
* {{mathworld|urlname=AbnormalNumber|title=Abnormal number}}
* {{mathworld|urlname=FundamentalTheoremofArithmetic|title=Fundamental Theorem of Arithmetic}}
== External links ==
* [https://gowers.wordpress.com/2011/11/13/why-isnt-the-fundamental-theorem-of-arithmetic-obvious Why isn’t the fundamental theorem of arithmetic obvious?]
* [http://www.cut-the-knot.org/blue/gcd_fta.shtml GCD and the Fundamental Theorem of Arithmetic] at [[cut-the-knot]].
* [http://planetmath.org/fundamentaltheoremofarithmeticproofofthe PlanetMath: Proof of fundamental theorem of arithmetic]
* [http://fermatslasttheorem.blogspot.com/2005/06/unique-factorization.html 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]].
* [http://demonstrations.wolfram.com/FundamentalTheoremOfArithmetic/ "Fundamental Theorem of Arithmetic"] by Hector Zenil, [[Wolfram Demonstrations Project]], 2007.
* {{cite web|last=Grime|first=James|title=1 and Prime Numbers|url=http://www.numberphile.com/videos/1notprime.html|work=Numberphile|publisher=[[Brady Haran]]}}
{{Fundamental theorems}}
{{Divisor classes}}
[[Category:Theorems about prime numbers]]
[[Category:Articles containing proofs]]
[[Category:Fundamental theorems|Arithmetic]]
[[de:Primfaktorzerlegung#Fundamentalsatz der Arithmetik]]' |
New page wikitext, after the edit (new_wikitext) | 'AND I OOP SKSKSKSK
==Euclid's original version==
Book VII, propositions 30, 31 and 32, and Book IX, proposition 14 of [[Euclid]]'s ''[[Euclid's Elements|Elements]]'' are essentially the statement and proof of the fundamental theorem.
{{Quotation|
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|[[#CITEREFEuclidHeath1956|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.
{{Quotation|
Any composite number is measured by some prime number.
|Euclid|[[#CITEREFEuclidHeath1956|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 [[Proof by infinite descent|infinite descent]].
{{Quotation|
Any number either is prime or is measured by some prime number.
|Euclid|[[#CITEREFEuclidHeath1956|Elements Book VII]], Proposition 32}}
Proposition 32 is derived from proposition 31, and proves that the decomposition is possible.
{{Quotation|
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|[[#CITEREFEuclidHeath1956|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]].<ref>{{Harvtxt|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."</ref> Indeed, in this proposition the exponents are all equal to one, so nothing is said for the general case.
Article 16 of [[Carl Friedrich Gauss|Gauss]]' ''[[Disquisitiones Arithmeticae]]'' is an early modern statement and proof employing [[modular arithmetic]].<ref name="Gauss1801.loc=16" />
==Applications==
===Canonical representation of a positive integer=== <!-- Redirect [[Canonical form]] links here -->
Every positive integer ''n'' > 1 can be represented in exactly one way as a product of prime powers:
:<math>
n = p_1^{n_1}p_2^{n_2} \cdots p_k^{n_k}
= \prod_{i=1}^{k} p_i^{n_i}
</math>
where {{nowrap begin}}''p''<sub>1</sub> < ''p''<sub>2</sub> < ... < ''p''<sub>k</sub>{{nowrap end}} are primes and the ''n''<sub>''i''</sub> 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'''<ref>{{harvtxt|Long|1972|p=45}}</ref> of ''n'', or the '''standard form'''<ref>{{harvtxt|Pettofrezzo|Byrkit|1970|p=55}}</ref><ref>{{Harvtxt|Hardy|Wright|2008|loc=§ 1.2}}</ref> of ''n''. For example,
:999 = 3<sup>3</sup>×37,
:1000 = 2<sup>3</sup>×5<sup>3</sup>,
:1001 = 7×11×13.
Note that factors ''p''<sup>0</sup> = 1 may be inserted without changing the value of ''n'' (e.g., 1000 = 2<sup>3</sup>×3<sup>0</sup>×5<sup>3</sup>).<br>In fact, any positive integer can be uniquely represented as an [[infinite product]] taken over all the positive prime numbers:
:<math>
n=2^{n_1}3^{n_2}5^{n_3}7^{n_4}\cdots=\prod_{i=1}^\infty p_i^{n_i},
</math>
where a finite number of the ''n''<sub>''i''</sub> are positive integers, and the rest are zero. Allowing negative exponents provides a canonical form for positive [[rational number]]s.
===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:
:<math>\begin{alignat}{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{alignat}</math>
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===
{{Main article|Arithmetic function}}
Many arithmetic functions are defined using the canonical representation. In particular, the values of [[additive function|additive]] and [[multiplicative function|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'' [[Divisor|divides]] the product of two [[natural number]]s ''a'' and ''b'', then ''p'' divides ''a'' or ''p'' divides ''b''.
===Existence===
It must be shown that every integer greater than 1 is either prime or a product of primes. First, 2 is prime. Then, by [[strong induction]], assume this is true for all numbers greater than 1 and less than ''n''. If ''n'' is prime, there is nothing more to prove. Otherwise, there are integers ''a'' and ''b'', where ''n'' = ''ab'', and {{nowrap|1 < ''a'' ≤ ''b'' < ''n''}}. By the induction hypothesis, {{nowrap|1=''a'' = ''p''<sub>1</sub>''p''<sub>2</sub>...''p''<sub>''j''</sub>}} and {{nowrap|1=''b'' = ''q''<sub>1</sub>''q''<sub>2</sub>...''q''<sub>''k''</sub>}} are products of primes. But then {{nowrap|1=''n'' = ''ab'' = ''p''<sub>1</sub>''p''<sub>2</sub>...''p''<sub>''j''</sub>''q''<sub>1</sub>''q''<sub>2</sub>...''q''<sub>''k''</sub>}} is a product of primes.
===Uniqueness===
Suppose, to the contrary, there is an integer that has two distinct prime factorizations. Let ''n'' be the least such integer and write ''n'' = ''p''<sub>1</sub> ''p''<sub>2</sub> ... ''p''<sub>''j''</sub> = ''q''<sub>1</sub> ''q''<sub>2</sub> ... ''q''<sub>''k''</sub>, where each ''p''<sub>''i''</sub> and ''q''<sub>''i''</sub> is prime. (Note ''j'' and ''k'' are both at least 2.) We see ''p''<sub>1</sub> divides ''q''<sub>1</sub> ''q''<sub>2</sub> ... ''q''<sub>''k''</sub>, so ''p''<sub>1</sub> divides some ''q''<sub>''i''</sub> by Euclid's lemma. Without loss of generality, say ''p''<sub>1</sub> divides ''q''<sub>1</sub>. Since ''p''<sub>1</sub> and ''q''<sub>1</sub> are both prime, it follows that ''p''<sub>1</sub> = ''q''<sub>1</sub>. Returning to our factorizations of ''n'', we may cancel these two terms to conclude ''p''<sub>2</sub> ... ''p''<sub>''j''</sub> = ''q''<sub>2</sub> ... ''q''<sub>''k''</sub>. We now have two distinct prime factorizations of some integer strictly smaller than ''n'', which contradicts the minimality of ''n''.
===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'':
:<math>
\begin{align}
s
&=p_1 p_2 \cdots p_m \\
&=q_1 q_2 \cdots q_n.
\end{align}
</math>
If any ''p''<sub>''i''</sub> = ''q''<sub>''j''</sub> then, by cancellation, ''s''/''p''<sub>''i''</sub> = ''s''/''q''<sub>''j''</sub> would be another positive integer, different from s, which is greater than 1 and also has two distinct factorizations. But ''s''/''p''<sub>''i''</sub> is smaller than ''s'', meaning ''s'' would not actually be the smallest such integer. Therefore every ''p''<sub>''i''</sub> must be distinct from every ''q''<sub>''j''</sub>.
Without loss of generality, take ''p''<sub>1</sub> < ''q''<sub>1</sub> (if this is not already the case, switch the ''p'' and ''q'' designations.) Consider
:<math>t = (q_1 - p_1)(q_2 \cdots q_n),</math>
and note that 1 < ''q''<sub>2</sub> ≤ ''t'' < ''s''. Therefore ''t'' must have a unique prime factorization. By rearrangement we see,
:<math>
\begin{align}
t
&= q_1(q_2 \cdots q_n) - p_1(q_2 \cdots q_n) \\
&= s - p_1(q_2 \cdots q_n) \\
&= p_1((p_2 \cdots p_m) - (q_2 \cdots q_n)).
\end{align}
</math>
Here ''u'' = ((''p''<sub>2</sub> ... ''p''<sub>''m''</sub>) - (''q''<sub>2</sub> ... ''q''<sub>''n''</sub>)) is positive, for if it were negative or zero then so would be its product with ''p''<sub>''1''</sub>, but that product equals ''t'' which is positive. So ''u'' is either 1 or factors into primes. In either case, ''t'' = ''p''<sub>1</sub>''u'' yields a prime factorization of ''t'', which we know to be unique, so ''p''<sub>1</sub> appears in the prime factorization of ''t''.
If (''q''<sub>1</sub> - ''p''<sub>1</sub>) equaled 1 then the prime factorization of ''t'' would be all ''q'''s, which would preclude ''p''<sub>1</sub> from appearing. Thus (''q''<sub>1</sub> - ''p''<sub>1</sub>) is not 1, but is positive, so it factors into primes: (''q''<sub>1</sub> - ''p''<sub>1</sub>) = (''r''<sub>1</sub> ... ''r''<sub>''h''</sub>). This yields a prime factorization of
:<math>t = (r_1 \cdots r_h)(q_2 \cdots q_n),</math>
which we know is unique. Now, ''p''<sub>1</sub> 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''<sub>1</sub> is a factor of (''q''<sub>1</sub> - ''p''<sub>1</sub>), so there exists a positive integer ''k'' such that ''p''<sub>1</sub>''k'' = (''q''<sub>1</sub> - ''p''<sub>1</sub>), and therefore
:<math>p_1(k+1) = q_1.</math>
But that means ''q''<sub>1</sub> 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 theory|ring]] of [[Gaussian integer]]s, the set of all [[complex number]]s ''a'' + ''bi'' where ''a'' and ''b'' are integers. It is now denoted by <math>\mathbb{Z}[i].</math> 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.<ref>[[#CITEREFGauss1832|Gauss, BQ, §§ 31–34]]</ref>
Similarly, in 1844 while working on [[cubic reciprocity]], [[Gotthold Eisenstein|Eisenstein]] introduced the ring <math>\mathbb{Z}[\omega]</math>, where <math>\omega=\frac{-1+\sqrt{-3}}{2}, </math> <math>\omega^3=1 </math> is a cube [[root of unity]]. This is the ring of [[Eisenstein integer]]s, and he proved it has the six units <math>\pm 1, \pm\omega, \pm\omega^2</math> and that it has unique factorization.
However, it was also discovered that unique factorization does not always hold. An example is given by <math>\mathbb{Z}[\sqrt{-5}]</math>. In this ring one has<ref>{{Harvtxt|Hardy|Wright|2008|loc=§ 14.6}}</ref>
:<math>
6=
2\cdot 3=
(1+\sqrt{-5})(1-\sqrt{-5}).
</math>
Examples like this caused the notion of "prime" to be modified. In <math>\mathbb{Z}[\sqrt{-5}]</math> 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 + {{sqrt|−5}}) nor (1 − {{sqrt|−5}}) even though it divides their product 6. In [[algebraic number theory]] 2 is called [[irreducible element|irreducible]] in <math>\mathbb{Z}[\sqrt{-5}]</math> (only divisible by itself or a unit) but not [[prime element|prime]] in <math>\mathbb{Z}[\sqrt{-5}]</math> (if it divides a product it must divide one of the factors). The mention of <math>\mathbb{Z}[\sqrt{-5}]</math> is required because 2 is prime and irreducible in <math>\mathbb{Z}.</math> Using these definitions it can be proven that in any [[integral domain]] a prime must be irreducible. Euclid's classical lemma can be rephrased as "in the ring of integers <math>\mathbb{Z}</math> every irreducible is prime". This is also true in <math>\mathbb{Z}[i]</math> and <math>\mathbb{Z}[\omega],</math> but not in <math>\mathbb{Z}[\sqrt{-5}].</math>
The rings in which factorization into irreducibles is essentially unique are called [[unique factorization domain]]s. Important examples are [[polynomial ring]]s over the integers or over a [[field (mathematics)|field]], [[Euclidean domain]]s and [[principal ideal domain]]s.
In 1843 [[Ernst Kummer|Kummer]] introduced the concept of [[ideal number]], which was developed further by [[Richard Dedekind|Dedekind]] (1876) into the modern theory of [[Ideal (ring theory)|ideals]], special subsets of rings. Multiplication is defined for ideals, and the rings in which they have unique factorization are called [[Dedekind domain]]s.
There is a version of [[ordinal arithmetic|unique factorization for ordinals]], though it requires some additional conditions to ensure uniqueness.
==See also==
* [[Riemann zeta function#Euler product formula|Euler product formula]]
* [[Integer factorization]]
* [[Noetherian ring]]
* [[Prime signature]]
==Notes==
{{reflist|30em}}
==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.
* {{citation
| last1 = Gauss | first1 = Carl Friedrich
| last2 = Clarke | first2 = Arthur A. (translator into English)
| title = Disquisitiones Arithemeticae (Second, corrected edition)
| publisher = [[Springer Science+Business Media|Springer]]
| location = New York
| year = 1986
| isbn = 978-0-387-96254-2
| url = https://www.springer.com/mathematics/algebra/book/978-0-387-96254-2
}}
* {{citation
| last1 = Gauss | first1 = Carl Friedrich
| last2 = Maser | first2 = H. (translator into German)
| title = Untersuchungen über hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition)
| publisher = Chelsea
| location = New York
| year = 1965
| 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''".
* {{citation
| last1 = Gauss | first1 = Carl Friedrich
| title = Theoria residuorum biquadraticorum, Commentatio prima
| publisher = Comment. Soc. regiae sci, Göttingen 6
| location = Göttingen
| year = 1828}}
* {{citation
| last1 = Gauss | first1 = Carl Friedrich
| title = Theoria residuorum biquadraticorum, Commentatio secunda
| publisher = Comment. Soc. regiae sci, Göttingen 7
| location = Göttingen
| year = 1832}}
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''.
* {{Citation
| last=Baker
| first=Alan
| author-link=
| year=1984
| title=A Concise Introduction to the Theory of Numbers
| place=Cambridge, UK
| publisher=Cambridge University Press
| isbn=978-0-521-28654-1
}}
* {{citation
| author1 = Euclid
| author1-link = Euclid
| others = Translated by [[Thomas Little Heath]]
| title = The thirteen books of the Elements
| edition = Second Edition Unabridged
| volume = 2 (Books III-IX)
| publisher = [[Dover]]
| location = New York
| year = 1956
| isbn = 978-0-486-60089-5
| url = http://store.doverpublications.com/0486600890.html
}}
* {{Hardy and Wright}}
* {{Citation
| author1 = A. Kornilowicz
| author2 = P. Rudnicki
| year = 2004
| title = Fundamental theorem of arithmetic
| journal = [[Formalized Mathematics]]
| volume = 12
| issue = 2
| pages = 179–185
}}
* {{citation
| first1 = Calvin T.
| last1 = Long
| year = 1972
| title = Elementary Introduction to Number Theory
| edition = 2nd | publisher = [[D. C. Heath and Company]]
| location = Lexington
| lccn = 77-171950
}}.
* {{citation
| first1 = Anthony J.
| last1 = Pettofrezzo
| first2 = Donald R.
| last2 = Byrkit
| year = 1970
| title = Elements of Number Theory
| publisher = [[Prentice Hall]]
| location = Englewood Cliffs
| lccn = 77-81766
}}.
* {{citation
| last1 = Riesel | first1 = Hans
| title = Prime Numbers and Computer Methods for Factorization (second edition)
| publisher = Birkhäuser
| location = Boston
| year = 1994
| isbn = 0-8176-3743-5}}
* {{Cite book |last= Weil |first= André |year= 2007 |origyear= 1984 |title= [[Number Theory: An Approach through History from Hammurapi to Legendre]] |series= Modern Birkhäuser Classics |location= Boston, MA |publisher= Birkhäuser |isbn= 978-0-817-64565-6 |ref= harv }}
* {{mathworld|urlname=AbnormalNumber|title=Abnormal number}}
* {{mathworld|urlname=FundamentalTheoremofArithmetic|title=Fundamental Theorem of Arithmetic}}
== External links ==
* [https://gowers.wordpress.com/2011/11/13/why-isnt-the-fundamental-theorem-of-arithmetic-obvious Why isn’t the fundamental theorem of arithmetic obvious?]
* [http://www.cut-the-knot.org/blue/gcd_fta.shtml GCD and the Fundamental Theorem of Arithmetic] at [[cut-the-knot]].
* [http://planetmath.org/fundamentaltheoremofarithmeticproofofthe PlanetMath: Proof of fundamental theorem of arithmetic]
* [http://fermatslasttheorem.blogspot.com/2005/06/unique-factorization.html 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]].
* [http://demonstrations.wolfram.com/FundamentalTheoremOfArithmetic/ "Fundamental Theorem of Arithmetic"] by Hector Zenil, [[Wolfram Demonstrations Project]], 2007.
* {{cite web|last=Grime|first=James|title=1 and Prime Numbers|url=http://www.numberphile.com/videos/1notprime.html|work=Numberphile|publisher=[[Brady Haran]]}}
{{Fundamental theorems}}
{{Divisor classes}}
[[Category:Theorems about prime numbers]]
[[Category:Articles containing proofs]]
[[Category:Fundamental theorems|Arithmetic]]
[[de:Primfaktorzerlegung#Fundamentalsatz der Arithmetik]]' |
Parsed HTML source of the new revision (new_html) | '<div class="mw-parser-output"><p>AND I OOP SKSKSKSK
</p>
<div id="toc" class="toc"><input type="checkbox" role="button" id="toctogglecheckbox" class="toctogglecheckbox" style="display:none" /><div class="toctitle" lang="en" dir="ltr"><h2>Contents</h2><span class="toctogglespan"><label class="toctogglelabel" for="toctogglecheckbox"></label></span></div>
<ul>
<li class="toclevel-1 tocsection-1"><a href="#Euclid's_original_version"><span class="tocnumber">1</span> <span class="toctext">Euclid's original version</span></a></li>
<li class="toclevel-1 tocsection-2"><a href="#Applications"><span class="tocnumber">2</span> <span class="toctext">Applications</span></a>
<ul>
<li class="toclevel-2 tocsection-3"><a href="#Canonical_representation_of_a_positive_integer"><span class="tocnumber">2.1</span> <span class="toctext">Canonical representation of a positive integer</span></a></li>
<li class="toclevel-2 tocsection-4"><a href="#Arithmetic_operations"><span class="tocnumber">2.2</span> <span class="toctext">Arithmetic operations</span></a></li>
<li class="toclevel-2 tocsection-5"><a href="#Arithmetic_functions"><span class="tocnumber">2.3</span> <span class="toctext">Arithmetic functions</span></a></li>
</ul>
</li>
<li class="toclevel-1 tocsection-6"><a href="#Proof"><span class="tocnumber">3</span> <span class="toctext">Proof</span></a>
<ul>
<li class="toclevel-2 tocsection-7"><a href="#Existence"><span class="tocnumber">3.1</span> <span class="toctext">Existence</span></a></li>
<li class="toclevel-2 tocsection-8"><a href="#Uniqueness"><span class="tocnumber">3.2</span> <span class="toctext">Uniqueness</span></a></li>
<li class="toclevel-2 tocsection-9"><a href="#Elementary_proof_of_uniqueness"><span class="tocnumber">3.3</span> <span class="toctext">Elementary proof of uniqueness</span></a></li>
</ul>
</li>
<li class="toclevel-1 tocsection-10"><a href="#Generalizations"><span class="tocnumber">4</span> <span class="toctext">Generalizations</span></a></li>
<li class="toclevel-1 tocsection-11"><a href="#See_also"><span class="tocnumber">5</span> <span class="toctext">See also</span></a></li>
<li class="toclevel-1 tocsection-12"><a href="#Notes"><span class="tocnumber">6</span> <span class="toctext">Notes</span></a></li>
<li class="toclevel-1 tocsection-13"><a href="#References"><span class="tocnumber">7</span> <span class="toctext">References</span></a></li>
<li class="toclevel-1 tocsection-14"><a href="#External_links"><span class="tocnumber">8</span> <span class="toctext">External links</span></a></li>
</ul>
</div>
<h2><span id="Euclid.27s_original_version"></span><span class="mw-headline" id="Euclid's_original_version">Euclid's original version</span><span class="mw-editsection"><a href="/w/index.php?title=Special:Badtitle/dummy_title_for_API_calls_set_in_api.php&action=edit&section=1" title="Edit section: Euclid's original version" data-section="1" class="mw-ui-icon mw-ui-icon-element mw-ui-icon-minerva-edit-enabled edit-page">Edit</a></span></h2>
<p>Book VII, propositions 30, 31 and 32, and Book IX, proposition 14 of <a href="/wiki/Euclid" title="Euclid">Euclid</a>'s <i><a href="/wiki/Euclid%27s_Elements" title="Euclid's Elements">Elements</a></i> are essentially the statement and proof of the fundamental theorem.
</p>
<style data-mw-deduplicate="TemplateStyles:r886047036">.mw-parser-output .templatequote{overflow:hidden;margin:1em 0;padding:0 40px}.mw-parser-output .templatequote .templatequotecite{line-height:1.5em;text-align:left;padding-left:1.6em;margin-top:0}</style><blockquote class="templatequote"><p>If two numbers by multiplying one another make some
</p><p>number, and any prime number measure the product, it will
</p><p>
also measure one of the original numbers.</p><div class="templatequotecite">— <cite>Euclid, <a href="#CITEREFEuclidHeath1956">Elements Book VII</a>, Proposition 30</cite></div>
</blockquote>
<p>(In modern terminology: if a prime <i>p</i> divides the product <i>ab</i>, then <i>p</i> divides either <i>a</i> or <i>b</i> or both.) Proposition 30 is referred to as <a href="/wiki/Euclid%27s_lemma" title="Euclid's lemma">Euclid's lemma</a>, and it is the key in the proof of the fundamental theorem of arithmetic.
</p>
<link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r886047036"/><blockquote class="templatequote"><p>Any composite number is measured by some prime number.</p><div class="templatequotecite">— <cite>Euclid, <a href="#CITEREFEuclidHeath1956">Elements Book VII</a>, Proposition 31</cite></div>
</blockquote>
<p>(In modern terminology: every integer greater than one is divided evenly by some prime number.) Proposition 31 is proved directly by <a href="/wiki/Proof_by_infinite_descent" title="Proof by infinite descent">infinite descent</a>.
</p>
<link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r886047036"/><blockquote class="templatequote"><p>Any number either is prime or is measured by some prime number.</p><div class="templatequotecite">— <cite>Euclid, <a href="#CITEREFEuclidHeath1956">Elements Book VII</a>, Proposition 32</cite></div>
</blockquote>
<p>Proposition 32 is derived from proposition 31, and proves that the decomposition is possible.
</p>
<link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r886047036"/><blockquote class="templatequote"><p>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.</p><div class="templatequotecite">— <cite>Euclid, <a href="#CITEREFEuclidHeath1956">Elements Book IX</a>, Proposition 14</cite></div>
</blockquote>
<p>(In modern terminology: a <a href="/wiki/Least_common_multiple" title="Least common multiple">least common multiple</a> 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 <a href="/wiki/Andr%C3%A9_Weil" title="André Weil">André Weil</a>.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1">[1]</a></sup> Indeed, in this proposition the exponents are all equal to one, so nothing is said for the general case.
</p><p>Article 16 of <a href="/wiki/Carl_Friedrich_Gauss" title="Carl Friedrich Gauss">Gauss</a>' <i><a href="/wiki/Disquisitiones_Arithmeticae" title="Disquisitiones Arithmeticae">Disquisitiones Arithmeticae</a></i> is an early modern statement and proof employing <a href="/wiki/Modular_arithmetic" title="Modular arithmetic">modular arithmetic</a>.<sup id="cite_ref-Gauss1801.loc=16_2-0" class="reference"><a href="#cite_note-Gauss1801.loc=16-2">[2]</a></sup>
</p>
<h2><span class="mw-headline" id="Applications">Applications</span><span class="mw-editsection"><a href="/w/index.php?title=Special:Badtitle/dummy_title_for_API_calls_set_in_api.php&action=edit&section=2" title="Edit section: Applications" data-section="2" class="mw-ui-icon mw-ui-icon-element mw-ui-icon-minerva-edit-enabled edit-page">Edit</a></span></h2>
<h3><span class="mw-headline" id="Canonical_representation_of_a_positive_integer">Canonical representation of a positive integer</span><span class="mw-editsection"><a href="/w/index.php?title=Special:Badtitle/dummy_title_for_API_calls_set_in_api.php&action=edit&section=3" title="Edit section: Canonical representation of a positive integer" data-section="3" class="mw-ui-icon mw-ui-icon-element mw-ui-icon-minerva-edit-enabled edit-page">Edit</a></span></h3>
<p>Every positive integer <i>n</i> > 1 can be represented in exactly one way as a product of prime powers:
</p>
<dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=p_{1}^{n_{1}}p_{2}^{n_{2}}\cdots p_{k}^{n_{k}}=\prod _{i=1}^{k}p_{i}^{n_{i}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
<mo>=</mo>
<msubsup>
<mi>p</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<msub>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
</mrow>
</msubsup>
<msubsup>
<mi>p</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<msub>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
</mrow>
</msubsup>
<mo>⋯<!-- ⋯ --></mo>
<msubsup>
<mi>p</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>k</mi>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<msub>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>k</mi>
</mrow>
</msub>
</mrow>
</msubsup>
<mo>=</mo>
<munderover>
<mo>∏<!-- ∏ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mi>k</mi>
</mrow>
</munderover>
<msubsup>
<mi>p</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<msub>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mrow>
</msubsup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n=p_{1}^{n_{1}}p_{2}^{n_{2}}\cdots p_{k}^{n_{k}}=\prod _{i=1}^{k}p_{i}^{n_{i}}}</annotation>
</semantics>
</math></span><img src="/media/api/rest_v1/media/math/render/svg/22f8cf10ecd16a6f7dc6d97338d84be9c369a3f7" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -3.005ex; width:27.145ex; height:7.343ex;" alt="{\displaystyle n=p_{1}^{n_{1}}p_{2}^{n_{2}}\cdots p_{k}^{n_{k}}=\prod _{i=1}^{k}p_{i}^{n_{i}}}"/></span></dd></dl>
<p>where <span class="nowrap"><i>p</i><sub>1</sub> < <i>p</i><sub>2</sub> < ... < <i>p</i><sub>k</sub></span> are primes and the <i>n</i><sub><i>i</i></sub> are positive integers. This representation is commonly extended to all positive integers, including 1, by the convention that the <a href="/wiki/Empty_product" title="Empty product">empty product</a> is equal to 1 (the empty product corresponds to <i>k</i> = 0).
</p><p>This representation is called the <b>canonical representation</b><sup id="cite_ref-3" class="reference"><a href="#cite_note-3">[3]</a></sup> of <i>n</i>, or the <b>standard form</b><sup id="cite_ref-4" class="reference"><a href="#cite_note-4">[4]</a></sup><sup id="cite_ref-5" class="reference"><a href="#cite_note-5">[5]</a></sup> of <i>n</i>. For example,
</p>
<dl><dd>999 = 3<sup>3</sup>×37,</dd>
<dd>1000 = 2<sup>3</sup>×5<sup>3</sup>,</dd>
<dd>1001 = 7×11×13.</dd></dl>
<p>Note that factors <i>p</i><sup>0</sup> = 1 may be inserted without changing the value of <i>n</i> (e.g., 1000 = 2<sup>3</sup>×3<sup>0</sup>×5<sup>3</sup>).<br />In fact, any positive integer can be uniquely represented as an <a href="/wiki/Infinite_product" title="Infinite product">infinite product</a> taken over all the positive prime numbers:
</p>
<dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=2^{n_{1}}3^{n_{2}}5^{n_{3}}7^{n_{4}}\cdots =\prod _{i=1}^{\infty }p_{i}^{n_{i}},}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
<mo>=</mo>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<msub>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
</mrow>
</msup>
<msup>
<mn>3</mn>
<mrow class="MJX-TeXAtom-ORD">
<msub>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
</mrow>
</msup>
<msup>
<mn>5</mn>
<mrow class="MJX-TeXAtom-ORD">
<msub>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>3</mn>
</mrow>
</msub>
</mrow>
</msup>
<msup>
<mn>7</mn>
<mrow class="MJX-TeXAtom-ORD">
<msub>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>4</mn>
</mrow>
</msub>
</mrow>
</msup>
<mo>⋯<!-- ⋯ --></mo>
<mo>=</mo>
<munderover>
<mo>∏<!-- ∏ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="normal">∞<!-- ∞ --></mi>
</mrow>
</munderover>
<msubsup>
<mi>p</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<msub>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mrow>
</msubsup>
<mo>,</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n=2^{n_{1}}3^{n_{2}}5^{n_{3}}7^{n_{4}}\cdots =\prod _{i=1}^{\infty }p_{i}^{n_{i}},}</annotation>
</semantics>
</math></span><img src="/media/api/rest_v1/media/math/render/svg/96acf1f2e6f71cbd4675c76219fd7a519d03b64f" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -3.005ex; width:30.568ex; height:6.843ex;" alt="{\displaystyle n=2^{n_{1}}3^{n_{2}}5^{n_{3}}7^{n_{4}}\cdots =\prod _{i=1}^{\infty }p_{i}^{n_{i}},}"/></span></dd></dl>
<p>where a finite number of the <i>n</i><sub><i>i</i></sub> are positive integers, and the rest are zero. Allowing negative exponents provides a canonical form for positive <a href="/wiki/Rational_number" title="Rational number">rational numbers</a>.
</p>
<h3><span class="mw-headline" id="Arithmetic_operations">Arithmetic operations</span><span class="mw-editsection"><a href="/w/index.php?title=Special:Badtitle/dummy_title_for_API_calls_set_in_api.php&action=edit&section=4" title="Edit section: Arithmetic operations" data-section="4" class="mw-ui-icon mw-ui-icon-element mw-ui-icon-minerva-edit-enabled edit-page">Edit</a></span></h3>
<p>The canonical representations of the product, <a href="/wiki/Greatest_common_divisor" title="Greatest common divisor">greatest common divisor</a> (GCD), and <a href="/wiki/Least_common_multiple" title="Least common multiple">least common multiple</a> (LCM) of two numbers <i>a</i> and <i>b</i> can be expressed simply in terms of the canonical representations of <i>a</i> and <i>b</i> themselves:
</p>
<dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\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}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mtable columnalign="right left right left" rowspacing="3pt" columnspacing="0em 0em 0em 0em" displaystyle="true">
<mtr>
<mtd>
<mi>a</mi>
<mo>⋅<!-- ⋅ --></mo>
<mi>b</mi>
</mtd>
<mtd>
<mi></mi>
<mrow class="MJX-TeXAtom-ORD">
</mrow>
<mo>=</mo>
<mrow class="MJX-TeXAtom-ORD">
</mrow>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<msub>
<mi>a</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo>+</mo>
<msub>
<mi>b</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
</mrow>
</msup>
<msup>
<mn>3</mn>
<mrow class="MJX-TeXAtom-ORD">
<msub>
<mi>a</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo>+</mo>
<msub>
<mi>b</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
</mrow>
</msup>
<msup>
<mn>5</mn>
<mrow class="MJX-TeXAtom-ORD">
<msub>
<mi>a</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>3</mn>
</mrow>
</msub>
<mo>+</mo>
<msub>
<mi>b</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>3</mn>
</mrow>
</msub>
</mrow>
</msup>
<msup>
<mn>7</mn>
<mrow class="MJX-TeXAtom-ORD">
<msub>
<mi>a</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>4</mn>
</mrow>
</msub>
<mo>+</mo>
<msub>
<mi>b</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>4</mn>
</mrow>
</msub>
</mrow>
</msup>
<mo>⋯<!-- ⋯ --></mo>
</mtd>
<mtd />
<mtd>
<mi></mi>
<mrow class="MJX-TeXAtom-ORD">
</mrow>
<mo>=</mo>
<mrow class="MJX-TeXAtom-ORD">
</mrow>
<mo>∏<!-- ∏ --></mo>
<msubsup>
<mi>p</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<msub>
<mi>a</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo>+</mo>
<msub>
<mi>b</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mrow>
</msubsup>
<mo>,</mo>
</mtd>
</mtr>
<mtr>
<mtd>
<mo movablelimits="true" form="prefix">gcd</mo>
<mo stretchy="false">(</mo>
<mi>a</mi>
<mo>,</mo>
<mi>b</mi>
<mo stretchy="false">)</mo>
</mtd>
<mtd>
<mi></mi>
<mrow class="MJX-TeXAtom-ORD">
</mrow>
<mo>=</mo>
<mrow class="MJX-TeXAtom-ORD">
</mrow>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mo movablelimits="true" form="prefix">min</mo>
<mo stretchy="false">(</mo>
<msub>
<mi>a</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo>,</mo>
<msub>
<mi>b</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
</mrow>
</msup>
<msup>
<mn>3</mn>
<mrow class="MJX-TeXAtom-ORD">
<mo movablelimits="true" form="prefix">min</mo>
<mo stretchy="false">(</mo>
<msub>
<mi>a</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo>,</mo>
<msub>
<mi>b</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
</mrow>
</msup>
<msup>
<mn>5</mn>
<mrow class="MJX-TeXAtom-ORD">
<mo movablelimits="true" form="prefix">min</mo>
<mo stretchy="false">(</mo>
<msub>
<mi>a</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>3</mn>
</mrow>
</msub>
<mo>,</mo>
<msub>
<mi>b</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>3</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
</mrow>
</msup>
<msup>
<mn>7</mn>
<mrow class="MJX-TeXAtom-ORD">
<mo movablelimits="true" form="prefix">min</mo>
<mo stretchy="false">(</mo>
<msub>
<mi>a</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>4</mn>
</mrow>
</msub>
<mo>,</mo>
<msub>
<mi>b</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>4</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
</mrow>
</msup>
<mo>⋯<!-- ⋯ --></mo>
</mtd>
<mtd />
<mtd>
<mi></mi>
<mrow class="MJX-TeXAtom-ORD">
</mrow>
<mo>=</mo>
<mrow class="MJX-TeXAtom-ORD">
</mrow>
<mo>∏<!-- ∏ --></mo>
<msubsup>
<mi>p</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mo movablelimits="true" form="prefix">min</mo>
<mo stretchy="false">(</mo>
<msub>
<mi>a</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo>,</mo>
<msub>
<mi>b</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo stretchy="false">)</mo>
</mrow>
</msubsup>
<mo>,</mo>
</mtd>
</mtr>
<mtr>
<mtd>
<mi>lcm</mi>
<mo>⁡<!-- --></mo>
<mo stretchy="false">(</mo>
<mi>a</mi>
<mo>,</mo>
<mi>b</mi>
<mo stretchy="false">)</mo>
</mtd>
<mtd>
<mi></mi>
<mrow class="MJX-TeXAtom-ORD">
</mrow>
<mo>=</mo>
<mrow class="MJX-TeXAtom-ORD">
</mrow>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mo movablelimits="true" form="prefix">max</mo>
<mo stretchy="false">(</mo>
<msub>
<mi>a</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo>,</mo>
<msub>
<mi>b</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
</mrow>
</msup>
<msup>
<mn>3</mn>
<mrow class="MJX-TeXAtom-ORD">
<mo movablelimits="true" form="prefix">max</mo>
<mo stretchy="false">(</mo>
<msub>
<mi>a</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo>,</mo>
<msub>
<mi>b</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
</mrow>
</msup>
<msup>
<mn>5</mn>
<mrow class="MJX-TeXAtom-ORD">
<mo movablelimits="true" form="prefix">max</mo>
<mo stretchy="false">(</mo>
<msub>
<mi>a</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>3</mn>
</mrow>
</msub>
<mo>,</mo>
<msub>
<mi>b</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>3</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
</mrow>
</msup>
<msup>
<mn>7</mn>
<mrow class="MJX-TeXAtom-ORD">
<mo movablelimits="true" form="prefix">max</mo>
<mo stretchy="false">(</mo>
<msub>
<mi>a</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>4</mn>
</mrow>
</msub>
<mo>,</mo>
<msub>
<mi>b</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>4</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
</mrow>
</msup>
<mo>⋯<!-- ⋯ --></mo>
</mtd>
<mtd />
<mtd>
<mi></mi>
<mrow class="MJX-TeXAtom-ORD">
</mrow>
<mo>=</mo>
<mrow class="MJX-TeXAtom-ORD">
</mrow>
<mo>∏<!-- ∏ --></mo>
<msubsup>
<mi>p</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mo movablelimits="true" form="prefix">max</mo>
<mo stretchy="false">(</mo>
<msub>
<mi>a</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo>,</mo>
<msub>
<mi>b</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo stretchy="false">)</mo>
</mrow>
</msubsup>
<mo>.</mo>
</mtd>
</mtr>
</mtable>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\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}}}</annotation>
</semantics>
</math></span><img src="/media/api/rest_v1/media/math/render/svg/181cc7d2f85a4c40cec2c8fed52b73d1e82cc38e" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -5.505ex; width:69.871ex; height:12.176ex;" alt="{\displaystyle {\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}}}"/></span></dd></dl>
<p>However, <a href="/wiki/Integer_factorization" title="Integer factorization">integer factorization</a>, especially of large numbers, is much more difficult than computing products, GCDs, or LCMs. So these formulas have limited use in practice.
</p>
<h3><span class="mw-headline" id="Arithmetic_functions">Arithmetic functions</span><span class="mw-editsection"><a href="/w/index.php?title=Special:Badtitle/dummy_title_for_API_calls_set_in_api.php&action=edit&section=5" title="Edit section: Arithmetic functions" data-section="5" class="mw-ui-icon mw-ui-icon-element mw-ui-icon-minerva-edit-enabled edit-page">Edit</a></span></h3>
<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="/wiki/Arithmetic_function" title="Arithmetic function">Arithmetic function</a></div>
<p>Many arithmetic functions are defined using the canonical representation. In particular, the values of <a href="/wiki/Additive_function" title="Additive function">additive</a> and <a href="/wiki/Multiplicative_function" title="Multiplicative function">multiplicative</a> functions are determined by their values on the powers of prime numbers.
</p>
<h2><span class="mw-headline" id="Proof">Proof</span><span class="mw-editsection"><a href="/w/index.php?title=Special:Badtitle/dummy_title_for_API_calls_set_in_api.php&action=edit&section=6" title="Edit section: Proof" data-section="6" class="mw-ui-icon mw-ui-icon-element mw-ui-icon-minerva-edit-enabled edit-page">Edit</a></span></h2>
<p>The proof uses <a href="/wiki/Euclid%27s_lemma" title="Euclid's lemma">Euclid's lemma</a> (<i>Elements</i> VII, 30): if a prime <i>p</i> <a href="/wiki/Divisor" title="Divisor">divides</a> the product of two <a href="/wiki/Natural_number" title="Natural number">natural numbers</a> <i>a</i> and <i>b</i>, then <i>p</i> divides <i>a</i> or <i>p</i> divides <i>b</i>.
</p>
<h3><span class="mw-headline" id="Existence">Existence</span><span class="mw-editsection"><a href="/w/index.php?title=Special:Badtitle/dummy_title_for_API_calls_set_in_api.php&action=edit&section=7" title="Edit section: Existence" data-section="7" class="mw-ui-icon mw-ui-icon-element mw-ui-icon-minerva-edit-enabled edit-page">Edit</a></span></h3>
<p>It must be shown that every integer greater than 1 is either prime or a product of primes. First, 2 is prime. Then, by <a href="/wiki/Strong_induction" class="mw-redirect" title="Strong induction">strong induction</a>, assume this is true for all numbers greater than 1 and less than <i>n</i>. If <i>n</i> is prime, there is nothing more to prove. Otherwise, there are integers <i>a</i> and <i>b</i>, where <i>n</i> = <i>ab</i>, and <span class="nowrap">1 < <i>a</i> ≤ <i>b</i> < <i>n</i></span>. By the induction hypothesis, <span class="nowrap"><i>a</i> = <i>p</i><sub>1</sub><i>p</i><sub>2</sub>...<i>p</i><sub><i>j</i></sub></span> and <span class="nowrap"><i>b</i> = <i>q</i><sub>1</sub><i>q</i><sub>2</sub>...<i>q</i><sub><i>k</i></sub></span> are products of primes. But then <span class="nowrap"><i>n</i> = <i>ab</i> = <i>p</i><sub>1</sub><i>p</i><sub>2</sub>...<i>p</i><sub><i>j</i></sub><i>q</i><sub>1</sub><i>q</i><sub>2</sub>...<i>q</i><sub><i>k</i></sub></span> is a product of primes.
</p>
<h3><span class="mw-headline" id="Uniqueness">Uniqueness</span><span class="mw-editsection"><a href="/w/index.php?title=Special:Badtitle/dummy_title_for_API_calls_set_in_api.php&action=edit&section=8" title="Edit section: Uniqueness" data-section="8" class="mw-ui-icon mw-ui-icon-element mw-ui-icon-minerva-edit-enabled edit-page">Edit</a></span></h3>
<p>Suppose, to the contrary, there is an integer that has two distinct prime factorizations. Let <i>n</i> be the least such integer and write <i>n</i> = <i>p</i><sub>1</sub> <i>p</i><sub>2</sub> ... <i>p</i><sub><i>j</i></sub> = <i>q</i><sub>1</sub> <i>q</i><sub>2</sub> ... <i>q</i><sub><i>k</i></sub>, where each <i>p</i><sub><i>i</i></sub> and <i>q</i><sub><i>i</i></sub> is prime. (Note <i>j</i> and <i>k</i> are both at least 2.) We see <i>p</i><sub>1</sub> divides <i>q</i><sub>1</sub> <i>q</i><sub>2</sub> ... <i>q</i><sub><i>k</i></sub>, so <i>p</i><sub>1</sub> divides some <i>q</i><sub><i>i</i></sub> by Euclid's lemma. Without loss of generality, say <i>p</i><sub>1</sub> divides <i>q</i><sub>1</sub>. Since <i>p</i><sub>1</sub> and <i>q</i><sub>1</sub> are both prime, it follows that <i>p</i><sub>1</sub> = <i>q</i><sub>1</sub>. Returning to our factorizations of <i>n</i>, we may cancel these two terms to conclude <i>p</i><sub>2</sub> ... <i>p</i><sub><i>j</i></sub> = <i>q</i><sub>2</sub> ... <i>q</i><sub><i>k</i></sub>. We now have two distinct prime factorizations of some integer strictly smaller than <i>n</i>, which contradicts the minimality of <i>n</i>.
</p>
<h3><span class="mw-headline" id="Elementary_proof_of_uniqueness">Elementary proof of uniqueness</span><span class="mw-editsection"><a href="/w/index.php?title=Special:Badtitle/dummy_title_for_API_calls_set_in_api.php&action=edit&section=9" title="Edit section: Elementary proof of uniqueness" data-section="9" class="mw-ui-icon mw-ui-icon-element mw-ui-icon-minerva-edit-enabled edit-page">Edit</a></span></h3>
<p>The fundamental theorem of arithmetic can also be proved without using Euclid's lemma, as follows:
</p><p>Assume that <i>s</i> > 1 is the smallest positive integer which is the product of prime numbers in two different ways. If <i>s</i> were prime then it would factor uniquely as itself, so there must be at least two primes in each factorization of <i>s</i>:
</p>
<dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}s&=p_{1}p_{2}\cdots p_{m}\\&=q_{1}q_{2}\cdots q_{n}.\end{aligned}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mtable columnalign="right left right left right left right left right left right left" rowspacing="3pt" columnspacing="0em 2em 0em 2em 0em 2em 0em 2em 0em 2em 0em" displaystyle="true">
<mtr>
<mtd>
<mi>s</mi>
</mtd>
<mtd>
<mi></mi>
<mo>=</mo>
<msub>
<mi>p</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<msub>
<mi>p</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo>⋯<!-- ⋯ --></mo>
<msub>
<mi>p</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>m</mi>
</mrow>
</msub>
</mtd>
</mtr>
<mtr>
<mtd />
<mtd>
<mi></mi>
<mo>=</mo>
<msub>
<mi>q</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<msub>
<mi>q</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo>⋯<!-- ⋯ --></mo>
<msub>
<mi>q</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo>.</mo>
</mtd>
</mtr>
</mtable>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}s&=p_{1}p_{2}\cdots p_{m}\\&=q_{1}q_{2}\cdots q_{n}.\end{aligned}}}</annotation>
</semantics>
</math></span><img src="/media/api/rest_v1/media/math/render/svg/00df449892db252de084f4d8351c752da1fc3b97" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -2.338ex; width:15.73ex; height:5.843ex;" alt="{\begin{aligned}s&=p_{1}p_{2}\cdots p_{m}\\&=q_{1}q_{2}\cdots q_{n}.\end{aligned}}"/></span></dd></dl>
<p>If any <i>p</i><sub><i>i</i></sub> = <i>q</i><sub><i>j</i></sub> then, by cancellation, <i>s</i>/<i>p</i><sub><i>i</i></sub> = <i>s</i>/<i>q</i><sub><i>j</i></sub> would be another positive integer, different from s, which is greater than 1 and also has two distinct factorizations. But <i>s</i>/<i>p</i><sub><i>i</i></sub> is smaller than <i>s</i>, meaning <i>s</i> would not actually be the smallest such integer. Therefore every <i>p</i><sub><i>i</i></sub> must be distinct from every <i>q</i><sub><i>j</i></sub>.
</p><p>Without loss of generality, take <i>p</i><sub>1</sub> < <i>q</i><sub>1</sub> (if this is not already the case, switch the <i>p</i> and <i>q</i> designations.) Consider
</p>
<dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t=(q_{1}-p_{1})(q_{2}\cdots q_{n}),}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>t</mi>
<mo>=</mo>
<mo stretchy="false">(</mo>
<msub>
<mi>q</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo>−<!-- − --></mo>
<msub>
<mi>p</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mo stretchy="false">(</mo>
<msub>
<mi>q</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo>⋯<!-- ⋯ --></mo>
<msub>
<mi>q</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mo>,</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle t=(q_{1}-p_{1})(q_{2}\cdots q_{n}),}</annotation>
</semantics>
</math></span><img src="/media/api/rest_v1/media/math/render/svg/6329ed483cdcde0b96d62be027b98b1bc9379cf3" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.838ex; width:23.203ex; height:2.843ex;" alt="t=(q_{1}-p_{1})(q_{2}\cdots q_{n}),"/></span></dd></dl>
<p>and note that 1 < <i>q</i><sub>2</sub> ≤ <i>t</i> < <i>s</i>. Therefore <i>t</i> must have a unique prime factorization. By rearrangement we see,
</p>
<dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}t&=q_{1}(q_{2}\cdots q_{n})-p_{1}(q_{2}\cdots q_{n})\\&=s-p_{1}(q_{2}\cdots q_{n})\\&=p_{1}((p_{2}\cdots p_{m})-(q_{2}\cdots q_{n})).\end{aligned}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mtable columnalign="right left right left right left right left right left right left" rowspacing="3pt" columnspacing="0em 2em 0em 2em 0em 2em 0em 2em 0em 2em 0em" displaystyle="true">
<mtr>
<mtd>
<mi>t</mi>
</mtd>
<mtd>
<mi></mi>
<mo>=</mo>
<msub>
<mi>q</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo stretchy="false">(</mo>
<msub>
<mi>q</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo>⋯<!-- ⋯ --></mo>
<msub>
<mi>q</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mo>−<!-- − --></mo>
<msub>
<mi>p</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo stretchy="false">(</mo>
<msub>
<mi>q</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo>⋯<!-- ⋯ --></mo>
<msub>
<mi>q</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo stretchy="false">)</mo>
</mtd>
</mtr>
<mtr>
<mtd />
<mtd>
<mi></mi>
<mo>=</mo>
<mi>s</mi>
<mo>−<!-- − --></mo>
<msub>
<mi>p</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo stretchy="false">(</mo>
<msub>
<mi>q</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo>⋯<!-- ⋯ --></mo>
<msub>
<mi>q</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo stretchy="false">)</mo>
</mtd>
</mtr>
<mtr>
<mtd />
<mtd>
<mi></mi>
<mo>=</mo>
<msub>
<mi>p</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo stretchy="false">(</mo>
<mo stretchy="false">(</mo>
<msub>
<mi>p</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo>⋯<!-- ⋯ --></mo>
<msub>
<mi>p</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>m</mi>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mo>−<!-- − --></mo>
<mo stretchy="false">(</mo>
<msub>
<mi>q</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo>⋯<!-- ⋯ --></mo>
<msub>
<mi>q</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mo stretchy="false">)</mo>
<mo>.</mo>
</mtd>
</mtr>
</mtable>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}t&=q_{1}(q_{2}\cdots q_{n})-p_{1}(q_{2}\cdots q_{n})\\&=s-p_{1}(q_{2}\cdots q_{n})\\&=p_{1}((p_{2}\cdots p_{m})-(q_{2}\cdots q_{n})).\end{aligned}}}</annotation>
</semantics>
</math></span><img src="/media/api/rest_v1/media/math/render/svg/456c155d37054dabb5c9f977a04aa1cc3a442974" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -4.005ex; width:32.238ex; height:9.176ex;" alt="{\displaystyle {\begin{aligned}t&=q_{1}(q_{2}\cdots q_{n})-p_{1}(q_{2}\cdots q_{n})\\&=s-p_{1}(q_{2}\cdots q_{n})\\&=p_{1}((p_{2}\cdots p_{m})-(q_{2}\cdots q_{n})).\end{aligned}}}"/></span></dd></dl>
<p>Here <i>u</i> = ((<i>p</i><sub>2</sub> ... <i>p</i><sub><i>m</i></sub>) - (<i>q</i><sub>2</sub> ... <i>q</i><sub><i>n</i></sub>)) is positive, for if it were negative or zero then so would be its product with <i>p</i><sub><i>1</i></sub>, but that product equals <i>t</i> which is positive. So <i>u</i> is either 1 or factors into primes. In either case, <i>t</i> = <i>p</i><sub>1</sub><i>u</i> yields a prime factorization of <i>t</i>, which we know to be unique, so <i>p</i><sub>1</sub> appears in the prime factorization of <i>t</i>.
</p><p>If (<i>q</i><sub>1</sub> - <i>p</i><sub>1</sub>) equaled 1 then the prime factorization of <i>t</i> would be all <i>q'</i>s, which would preclude <i>p</i><sub>1</sub> from appearing. Thus (<i>q</i><sub>1</sub> - <i>p</i><sub>1</sub>) is not 1, but is positive, so it factors into primes: (<i>q</i><sub>1</sub> - <i>p</i><sub>1</sub>) = (<i>r</i><sub>1</sub> ... <i>r</i><sub><i>h</i></sub>). This yields a prime factorization of
</p>
<dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t=(r_{1}\cdots r_{h})(q_{2}\cdots q_{n}),}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>t</mi>
<mo>=</mo>
<mo stretchy="false">(</mo>
<msub>
<mi>r</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo>⋯<!-- ⋯ --></mo>
<msub>
<mi>r</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>h</mi>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mo stretchy="false">(</mo>
<msub>
<mi>q</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo>⋯<!-- ⋯ --></mo>
<msub>
<mi>q</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mo>,</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle t=(r_{1}\cdots r_{h})(q_{2}\cdots q_{n}),}</annotation>
</semantics>
</math></span><img src="/media/api/rest_v1/media/math/render/svg/6df14811c2bb1fe71ac407162d1fac55910c4e90" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.838ex; width:23.876ex; height:2.843ex;" alt="t=(r_{1}\cdots r_{h})(q_{2}\cdots q_{n}),"/></span></dd></dl>
<p>which we know is unique. Now, <i>p</i><sub>1</sub> appears in the prime factorization of <i>t</i>, and it is not equal to any <i>q</i>, so it must be one of the <i>r'</i>s. That means <i>p</i><sub>1</sub> is a factor of (<i>q</i><sub>1</sub> - <i>p</i><sub>1</sub>), so there exists a positive integer <i>k</i> such that <i>p</i><sub>1</sub><i>k</i> = (<i>q</i><sub>1</sub> - <i>p</i><sub>1</sub>), and therefore
</p>
<dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{1}(k+1)=q_{1}.}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>p</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo stretchy="false">(</mo>
<mi>k</mi>
<mo>+</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>=</mo>
<msub>
<mi>q</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo>.</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle p_{1}(k+1)=q_{1}.}</annotation>
</semantics>
</math></span><img src="/media/api/rest_v1/media/math/render/svg/873dde7853048f7e679dabf02424b011ce7a5aa9" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:15.173ex; height:2.843ex;" alt="p_{1}(k+1)=q_{1}."/></span></dd></dl>
<p>But that means <i>q</i><sub>1</sub> has a proper factorization, so it is not a prime number. This contradiction shows that <i>s</i> 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.
</p>
<h2><span class="mw-headline" id="Generalizations">Generalizations</span><span class="mw-editsection"><a href="/w/index.php?title=Special:Badtitle/dummy_title_for_API_calls_set_in_api.php&action=edit&section=10" title="Edit section: Generalizations" data-section="10" class="mw-ui-icon mw-ui-icon-element mw-ui-icon-minerva-edit-enabled edit-page">Edit</a></span></h2>
<p>The first generalization of the theorem is found in Gauss's second monograph (1832) on <a href="/wiki/Biquadratic_reciprocity" class="mw-redirect" title="Biquadratic reciprocity">biquadratic reciprocity</a>. This paper introduced what is now called the <a href="/wiki/Ring_theory" title="Ring theory">ring</a> of <a href="/wiki/Gaussian_integer" title="Gaussian integer">Gaussian integers</a>, the set of all <a href="/wiki/Complex_number" title="Complex number">complex numbers</a> <i>a</i> + <i>bi</i> where <i>a</i> and <i>b</i> are integers. It is now denoted by <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} [i].}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">Z</mi>
</mrow>
<mo stretchy="false">[</mo>
<mi>i</mi>
<mo stretchy="false">]</mo>
<mo>.</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} [i].}</annotation>
</semantics>
</math></span><img src="/media/api/rest_v1/media/math/render/svg/03900897cdf515bbbc52879377653a871b9efc06" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.838ex; width:4.293ex; height:2.843ex;" alt="\mathbb {Z} [i]."/></span> He showed that this ring has the four units ±1 and ±<i>i</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.<sup id="cite_ref-6" class="reference"><a href="#cite_note-6">[6]</a></sup>
</p><p>Similarly, in 1844 while working on <a href="/wiki/Cubic_reciprocity" title="Cubic reciprocity">cubic reciprocity</a>, <a href="/wiki/Gotthold_Eisenstein" title="Gotthold Eisenstein">Eisenstein</a> introduced the ring <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} [\omega ]}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">Z</mi>
</mrow>
<mo stretchy="false">[</mo>
<mi>ω<!-- ω --></mi>
<mo stretchy="false">]</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} [\omega ]}</annotation>
</semantics>
</math></span><img src="/media/api/rest_v1/media/math/render/svg/7ae955a9a0d0f342fc73aaafe28af604d23267f7" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.838ex; width:4.29ex; height:2.843ex;" alt="\mathbb {Z} [\omega ]"/></span>, where <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \omega ={\frac {-1+{\sqrt {-3}}}{2}},}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>ω<!-- ω --></mi>
<mo>=</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mrow>
<mo>−<!-- − --></mo>
<mn>1</mn>
<mo>+</mo>
<mrow class="MJX-TeXAtom-ORD">
<msqrt>
<mo>−<!-- − --></mo>
<mn>3</mn>
</msqrt>
</mrow>
</mrow>
<mn>2</mn>
</mfrac>
</mrow>
<mo>,</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \omega ={\frac {-1+{\sqrt {-3}}}{2}},}</annotation>
</semantics>
</math></span><img src="/media/api/rest_v1/media/math/render/svg/9add578b5be4b9f7419432e8bec52c5e35fb4bbb" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -1.838ex; width:16.745ex; height:5.843ex;" alt="\omega ={\frac {-1+{\sqrt {-3}}}{2}},"/></span>   <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \omega ^{3}=1}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mi>ω<!-- ω --></mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>3</mn>
</mrow>
</msup>
<mo>=</mo>
<mn>1</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \omega ^{3}=1}</annotation>
</semantics>
</math></span><img src="/media/api/rest_v1/media/math/render/svg/4fb9d9d68cafe260162d4a9d60613ea9b841fb60" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.338ex; width:6.761ex; height:2.676ex;" alt="\omega ^{3}=1"/></span> is a cube <a href="/wiki/Root_of_unity" title="Root of unity">root of unity</a>. This is the ring of <a href="/wiki/Eisenstein_integer" title="Eisenstein integer">Eisenstein integers</a>, and he proved it has the six units <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pm 1,\pm \omega ,\pm \omega ^{2}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo>±<!-- ± --></mo>
<mn>1</mn>
<mo>,</mo>
<mo>±<!-- ± --></mo>
<mi>ω<!-- ω --></mi>
<mo>,</mo>
<mo>±<!-- ± --></mo>
<msup>
<mi>ω<!-- ω --></mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \pm 1,\pm \omega ,\pm \omega ^{2}}</annotation>
</semantics>
</math></span><img src="/media/api/rest_v1/media/math/render/svg/94ec390e7a53fb29473c21614c7ea0bf731ff743" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.671ex; width:12.601ex; height:3.009ex;" alt="\pm 1,\pm \omega ,\pm \omega ^{2}"/></span> and that it has unique factorization.
</p><p>However, it was also discovered that unique factorization does not always hold. An example is given by <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} [{\sqrt {-5}}]}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">Z</mi>
</mrow>
<mo stretchy="false">[</mo>
<mrow class="MJX-TeXAtom-ORD">
<msqrt>
<mo>−<!-- − --></mo>
<mn>5</mn>
</msqrt>
</mrow>
<mo stretchy="false">]</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} [{\sqrt {-5}}]}</annotation>
</semantics>
</math></span><img src="/media/api/rest_v1/media/math/render/svg/a37499ef27234d8a67a65932184280bb17301312" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.838ex; width:7.75ex; height:3.009ex;" alt="\mathbb {Z} [{\sqrt {-5}}]"/></span>. In this ring one has<sup id="cite_ref-7" class="reference"><a href="#cite_note-7">[7]</a></sup>
</p>
<dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 6=2\cdot 3=(1+{\sqrt {-5}})(1-{\sqrt {-5}}).}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>6</mn>
<mo>=</mo>
<mn>2</mn>
<mo>⋅<!-- ⋅ --></mo>
<mn>3</mn>
<mo>=</mo>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo>+</mo>
<mrow class="MJX-TeXAtom-ORD">
<msqrt>
<mo>−<!-- − --></mo>
<mn>5</mn>
</msqrt>
</mrow>
<mo stretchy="false">)</mo>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo>−<!-- − --></mo>
<mrow class="MJX-TeXAtom-ORD">
<msqrt>
<mo>−<!-- − --></mo>
<mn>5</mn>
</msqrt>
</mrow>
<mo stretchy="false">)</mo>
<mo>.</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 6=2\cdot 3=(1+{\sqrt {-5}})(1-{\sqrt {-5}}).}</annotation>
</semantics>
</math></span><img src="/media/api/rest_v1/media/math/render/svg/1b1cfc85b789c25369c60232e85b739a055e54cc" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.838ex; width:33.447ex; height:3.009ex;" alt="{\displaystyle 6=2\cdot 3=(1+{\sqrt {-5}})(1-{\sqrt {-5}}).}"/></span></dd></dl>
<p>Examples like this caused the notion of "prime" to be modified. In <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} [{\sqrt {-5}}]}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">Z</mi>
</mrow>
<mo stretchy="false">[</mo>
<mrow class="MJX-TeXAtom-ORD">
<msqrt>
<mo>−<!-- − --></mo>
<mn>5</mn>
</msqrt>
</mrow>
<mo stretchy="false">]</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} [{\sqrt {-5}}]}</annotation>
</semantics>
</math></span><img src="/media/api/rest_v1/media/math/render/svg/a37499ef27234d8a67a65932184280bb17301312" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.838ex; width:7.75ex; height:3.009ex;" alt="\mathbb {Z} [{\sqrt {-5}}]"/></span> it can be proven that if any of the factors above can be represented as a product, e.g., 2 = <i>ab</i>, then one of <i>a</i> or <i>b</i> 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 + <span class="nowrap">√<span style="border-top:1px solid; padding:0 0.1em;">−5</span></span>) nor (1 − <span class="nowrap">√<span style="border-top:1px solid; padding:0 0.1em;">−5</span></span>) even though it divides their product 6. In <a href="/wiki/Algebraic_number_theory" title="Algebraic number theory">algebraic number theory</a> 2 is called <a href="/wiki/Irreducible_element" title="Irreducible element">irreducible</a> in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} [{\sqrt {-5}}]}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">Z</mi>
</mrow>
<mo stretchy="false">[</mo>
<mrow class="MJX-TeXAtom-ORD">
<msqrt>
<mo>−<!-- − --></mo>
<mn>5</mn>
</msqrt>
</mrow>
<mo stretchy="false">]</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} [{\sqrt {-5}}]}</annotation>
</semantics>
</math></span><img src="/media/api/rest_v1/media/math/render/svg/a37499ef27234d8a67a65932184280bb17301312" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.838ex; width:7.75ex; height:3.009ex;" alt="\mathbb {Z} [{\sqrt {-5}}]"/></span> (only divisible by itself or a unit) but not <a href="/wiki/Prime_element" title="Prime element">prime</a> in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} [{\sqrt {-5}}]}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">Z</mi>
</mrow>
<mo stretchy="false">[</mo>
<mrow class="MJX-TeXAtom-ORD">
<msqrt>
<mo>−<!-- − --></mo>
<mn>5</mn>
</msqrt>
</mrow>
<mo stretchy="false">]</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} [{\sqrt {-5}}]}</annotation>
</semantics>
</math></span><img src="/media/api/rest_v1/media/math/render/svg/a37499ef27234d8a67a65932184280bb17301312" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.838ex; width:7.75ex; height:3.009ex;" alt="\mathbb {Z} [{\sqrt {-5}}]"/></span> (if it divides a product it must divide one of the factors). The mention of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} [{\sqrt {-5}}]}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">Z</mi>
</mrow>
<mo stretchy="false">[</mo>
<mrow class="MJX-TeXAtom-ORD">
<msqrt>
<mo>−<!-- − --></mo>
<mn>5</mn>
</msqrt>
</mrow>
<mo stretchy="false">]</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} [{\sqrt {-5}}]}</annotation>
</semantics>
</math></span><img src="/media/api/rest_v1/media/math/render/svg/a37499ef27234d8a67a65932184280bb17301312" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.838ex; width:7.75ex; height:3.009ex;" alt="\mathbb {Z} [{\sqrt {-5}}]"/></span> is required because 2 is prime and irreducible in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} .}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">Z</mi>
</mrow>
<mo>.</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} .}</annotation>
</semantics>
</math></span><img src="/media/api/rest_v1/media/math/render/svg/89f4f38f32c2068bca9dc701d13b03dd4a5d52ab" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.338ex; width:2.197ex; height:2.176ex;" alt="\mathbb {Z} ."/></span> Using these definitions it can be proven that in any <a href="/wiki/Integral_domain" title="Integral domain">integral domain</a> a prime must be irreducible. Euclid's classical lemma can be rephrased as "in the ring of integers <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">Z</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} }</annotation>
</semantics>
</math></span><img src="/media/api/rest_v1/media/math/render/svg/449494a083e0a1fda2b61c62b2f09b6bee4633dc" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.338ex; width:1.55ex; height:2.176ex;" alt="\mathbb {Z} "/></span> every irreducible is prime". This is also true in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} [i]}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">Z</mi>
</mrow>
<mo stretchy="false">[</mo>
<mi>i</mi>
<mo stretchy="false">]</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} [i]}</annotation>
</semantics>
</math></span><img src="/media/api/rest_v1/media/math/render/svg/9ffa94e9e2e6d9e5e5373d5fafb954b902743fde" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.838ex; width:3.646ex; height:2.843ex;" alt="\mathbb {Z} [i]"/></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} [\omega ],}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">Z</mi>
</mrow>
<mo stretchy="false">[</mo>
<mi>ω<!-- ω --></mi>
<mo stretchy="false">]</mo>
<mo>,</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} [\omega ],}</annotation>
</semantics>
</math></span><img src="/media/api/rest_v1/media/math/render/svg/0645ae396d9c6f03fd33508a10a838bd30741db0" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.838ex; width:4.937ex; height:2.843ex;" alt="\mathbb {Z} [\omega ],"/></span> but not in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} [{\sqrt {-5}}].}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">Z</mi>
</mrow>
<mo stretchy="false">[</mo>
<mrow class="MJX-TeXAtom-ORD">
<msqrt>
<mo>−<!-- − --></mo>
<mn>5</mn>
</msqrt>
</mrow>
<mo stretchy="false">]</mo>
<mo>.</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} [{\sqrt {-5}}].}</annotation>
</semantics>
</math></span><img src="/media/api/rest_v1/media/math/render/svg/b61cb2c7c704f5007aa548b630b3a05fa032f621" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.838ex; width:8.397ex; height:3.009ex;" alt="\mathbb {Z} [{\sqrt {-5}}]."/></span>
</p><p>The rings in which factorization into irreducibles is essentially unique are called <a href="/wiki/Unique_factorization_domain" title="Unique factorization domain">unique factorization domains</a>. Important examples are <a href="/wiki/Polynomial_ring" title="Polynomial ring">polynomial rings</a> over the integers or over a <a href="/wiki/Field_(mathematics)" title="Field (mathematics)">field</a>, <a href="/wiki/Euclidean_domain" title="Euclidean domain">Euclidean domains</a> and <a href="/wiki/Principal_ideal_domain" title="Principal ideal domain">principal ideal domains</a>.
</p><p>In 1843 <a href="/wiki/Ernst_Kummer" title="Ernst Kummer">Kummer</a> introduced the concept of <a href="/wiki/Ideal_number" title="Ideal number">ideal number</a>, which was developed further by <a href="/wiki/Richard_Dedekind" title="Richard Dedekind">Dedekind</a> (1876) into the modern theory of <a href="/wiki/Ideal_(ring_theory)" title="Ideal (ring theory)">ideals</a>, special subsets of rings. Multiplication is defined for ideals, and the rings in which they have unique factorization are called <a href="/wiki/Dedekind_domain" title="Dedekind domain">Dedekind domains</a>.
</p><p>There is a version of <a href="/wiki/Ordinal_arithmetic" title="Ordinal arithmetic">unique factorization for ordinals</a>, though it requires some additional conditions to ensure uniqueness.
</p>
<h2><span class="mw-headline" id="See_also">See also</span><span class="mw-editsection"><a href="/w/index.php?title=Special:Badtitle/dummy_title_for_API_calls_set_in_api.php&action=edit&section=11" title="Edit section: See also" data-section="11" class="mw-ui-icon mw-ui-icon-element mw-ui-icon-minerva-edit-enabled edit-page">Edit</a></span></h2>
<ul><li><a href="/wiki/Riemann_zeta_function#Euler_product_formula" title="Riemann zeta function">Euler product formula</a></li>
<li><a href="/wiki/Integer_factorization" title="Integer factorization">Integer factorization</a></li>
<li><a href="/wiki/Noetherian_ring" title="Noetherian ring">Noetherian ring</a></li>
<li><a href="/wiki/Prime_signature" title="Prime signature">Prime signature</a></li></ul>
<h2><span class="mw-headline" id="Notes">Notes</span><span class="mw-editsection"><a href="/w/index.php?title=Special:Badtitle/dummy_title_for_API_calls_set_in_api.php&action=edit&section=12" title="Edit section: Notes" data-section="12" class="mw-ui-icon mw-ui-icon-element mw-ui-icon-minerva-edit-enabled edit-page">Edit</a></span></h2>
<div class="reflist columns references-column-width" style="-moz-column-width: 30em; -webkit-column-width: 30em; column-width: 30em; list-style-type: decimal;">
<ol class="references">
<li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text"><a href="#CITEREFWeil2007">Weil (2007</a>, 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."</span>
</li>
<li id="cite_note-Gauss1801.loc=16-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-Gauss1801.loc=16_2-0">^</a></b></span> <span class="error mw-ext-cite-error" lang="en" dir="ltr">Cite error: The named reference <code>Gauss1801.loc=16</code> was invoked but never defined (see the <a href="/wiki/Help:Cite_errors/Cite_error_references_no_text" title="Help:Cite errors/Cite error references no text">help page</a>).
</span></li>
<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><a href="#CITEREFLong1972">Long (1972</a>, p. 45)</span>
</li>
<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><a href="#CITEREFPettofrezzoByrkit1970">Pettofrezzo & Byrkit (1970</a>, p. 55)</span>
</li>
<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><a href="#CITEREFHardyWright2008">Hardy & Wright (2008</a>, § 1.2)</span>
</li>
<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><a href="#CITEREFGauss1832">Gauss, BQ, §§ 31–34</a></span>
</li>
<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><a href="#CITEREFHardyWright2008">Hardy & Wright (2008</a>, § 14.6)</span>
</li>
</ol></div>
<h2><span class="mw-headline" id="References">References</span><span class="mw-editsection"><a href="/w/index.php?title=Special:Badtitle/dummy_title_for_API_calls_set_in_api.php&action=edit&section=13" title="Edit section: References" data-section="13" class="mw-ui-icon mw-ui-icon-element mw-ui-icon-minerva-edit-enabled edit-page">Edit</a></span></h2>
<p>The <i><a href="/wiki/Disquisitiones_Arithmeticae" title="Disquisitiones Arithmeticae">Disquisitiones Arithmeticae</a></i> 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.
</p>
<ul><li><cite id="CITEREFGaussClarke1986" class="citation">Gauss, Carl Friedrich; Clarke, Arthur A. (translator into English) (1986), <a rel="nofollow" class="external text" href="https://www.springer.com/mathematics/algebra/book/978-0-387-96254-2"><i>Disquisitiones Arithemeticae (Second, corrected edition)</i></a>, New York: <a href="/wiki/Springer_Science%2BBusiness_Media" title="Springer Science+Business Media">Springer</a>, <a href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> <a href="/wiki/Special:BookSources/978-0-387-96254-2" title="Special:BookSources/978-0-387-96254-2"><bdi>978-0-387-96254-2</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Disquisitiones+Arithemeticae+%28Second%2C+corrected+edition%29&rft.place=New+York&rft.pub=Springer&rft.date=1986&rft.isbn=978-0-387-96254-2&rft.aulast=Gauss&rft.aufirst=Carl+Friedrich&rft.au=Clarke%2C+Arthur+A.+%28translator+into+English%29&rft_id=https%3A%2F%2Fwww.springer.com%2Fmathematics%2Falgebra%2Fbook%2F978-0-387-96254-2&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFundamental+theorem+of+arithmetic" class="Z3988"></span><style data-mw-deduplicate="TemplateStyles:r886058088">.mw-parser-output cite.citation{font-style:inherit}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation .cs1-lock-free a{background:url("/media/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 a{background:url("/media/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 a{background:url("/media/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-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-ws-icon a{background:url("/media/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-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-maint{display:none;color:#33aa33;margin-left:0.3em}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}</style></li>
<li><cite id="CITEREFGaussMaser1965" class="citation">Gauss, Carl Friedrich; Maser, H. (translator into German) (1965), <i>Untersuchungen über hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition)</i>, New York: Chelsea, <a href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> <a href="/wiki/Special:BookSources/0-8284-0191-8" title="Special:BookSources/0-8284-0191-8"><bdi>0-8284-0191-8</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Untersuchungen+%C3%BCber+hohere+Arithmetik+%28Disquisitiones+Arithemeticae+%26+other+papers+on+number+theory%29+%28Second+edition%29&rft.place=New+York&rft.pub=Chelsea&rft.date=1965&rft.isbn=0-8284-0191-8&rft.aulast=Gauss&rft.aufirst=Carl+Friedrich&rft.au=Maser%2C+H.+%28translator+into+German%29&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFundamental+theorem+of+arithmetic" class="Z3988"></span><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r886058088"/></li></ul>
<p>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, § <i>n</i>". Footnotes referencing the <i>Disquisitiones Arithmeticae</i> are of the form "Gauss, DA, Art. <i>n</i>".
</p>
<ul><li><cite id="CITEREFGauss1828" class="citation">Gauss, Carl Friedrich (1828), <i>Theoria residuorum biquadraticorum, Commentatio prima</i>, Göttingen: Comment. Soc. regiae sci, Göttingen 6</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Theoria+residuorum+biquadraticorum%2C+Commentatio+prima&rft.place=G%C3%B6ttingen&rft.pub=Comment.+Soc.+regiae+sci%2C+G%C3%B6ttingen+6&rft.date=1828&rft.aulast=Gauss&rft.aufirst=Carl+Friedrich&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFundamental+theorem+of+arithmetic" class="Z3988"></span><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r886058088"/></li>
<li><cite id="CITEREFGauss1832" class="citation">Gauss, Carl Friedrich (1832), <i>Theoria residuorum biquadraticorum, Commentatio secunda</i>, Göttingen: Comment. Soc. regiae sci, Göttingen 7</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Theoria+residuorum+biquadraticorum%2C+Commentatio+secunda&rft.place=G%C3%B6ttingen&rft.pub=Comment.+Soc.+regiae+sci%2C+G%C3%B6ttingen+7&rft.date=1832&rft.aulast=Gauss&rft.aufirst=Carl+Friedrich&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFundamental+theorem+of+arithmetic" class="Z3988"></span><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r886058088"/></li></ul>
<p>These are in Gauss's <i>Werke</i>, Vol II, pp. 65–92 and 93–148; German translations are pp. 511–533 and 534–586 of the German edition of the <i>Disquisitiones</i>.
</p>
<ul><li><cite id="CITEREFBaker1984" class="citation">Baker, Alan (1984), <i>A Concise Introduction to the Theory of Numbers</i>, Cambridge, UK: Cambridge University Press, <a href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> <a href="/wiki/Special:BookSources/978-0-521-28654-1" title="Special:BookSources/978-0-521-28654-1"><bdi>978-0-521-28654-1</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=A+Concise+Introduction+to+the+Theory+of+Numbers&rft.place=Cambridge%2C+UK&rft.pub=Cambridge+University+Press&rft.date=1984&rft.isbn=978-0-521-28654-1&rft.aulast=Baker&rft.aufirst=Alan&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFundamental+theorem+of+arithmetic" class="Z3988"></span><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r886058088"/></li>
<li><cite id="CITEREFEuclid1956" class="citation"><a href="/wiki/Euclid" title="Euclid">Euclid</a> (1956), <a rel="nofollow" class="external text" href="http://store.doverpublications.com/0486600890.html"><i>The thirteen books of the Elements</i></a>, 2 (Books III-IX), Translated by <a href="/wiki/Thomas_Little_Heath" class="mw-redirect" title="Thomas Little Heath">Thomas Little Heath</a> (Second Edition Unabridged ed.), New York: <a href="/wiki/Dover" title="Dover">Dover</a>, <a href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> <a href="/wiki/Special:BookSources/978-0-486-60089-5" title="Special:BookSources/978-0-486-60089-5"><bdi>978-0-486-60089-5</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=The+thirteen+books+of+the+Elements&rft.place=New+York&rft.edition=Second+Edition+Unabridged&rft.pub=Dover&rft.date=1956&rft.isbn=978-0-486-60089-5&rft.au=Euclid&rft_id=http%3A%2F%2Fstore.doverpublications.com%2F0486600890.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFundamental+theorem+of+arithmetic" class="Z3988"></span><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r886058088"/></li>
<li><cite class="citation book"><a href="/wiki/G._H._Hardy" title="G. H. Hardy">Hardy, G. H.</a>; <a href="/wiki/E._M._Wright" title="E. M. Wright">Wright, E. M.</a> (2008) [1938]. <i>An Introduction to the Theory of Numbers</i>. Revised by <a href="/wiki/Roger_Heath-Brown" title="Roger Heath-Brown">D. R. Heath-Brown</a> and <a href="/wiki/Joseph_H._Silverman" title="Joseph H. Silverman">J. H. Silverman</a>. Foreword by <a href="/wiki/Andrew_Wiles" title="Andrew Wiles">Andrew Wiles</a>. (6th ed.). Oxford: <a href="/wiki/Oxford_University_Press" title="Oxford University Press">Oxford University Press</a>. <a href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> <a href="/wiki/Special:BookSources/978-0-19-921986-5" title="Special:BookSources/978-0-19-921986-5"><bdi>978-0-19-921986-5</bdi></a>. <a href="/wiki/Mathematical_Reviews" title="Mathematical Reviews">MR</a> <a rel="nofollow" class="external text" href="//www.ams.org/mathscinet-getitem?mr=2445243">2445243</a>. <a href="/wiki/Zentralblatt_MATH" title="Zentralblatt MATH">Zbl</a> <a rel="nofollow" class="external text" href="//zbmath.org/?format=complete&q=an:1159.11001">1159.11001</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=An+Introduction+to+the+Theory+of+Numbers&rft.place=Oxford&rft.edition=6th&rft.pub=Oxford+University+Press&rft.date=2008&rft_id=%2F%2Fzbmath.org%2F%3Fformat%3Dcomplete%26q%3Dan%3A1159.11001&rft_id=%2F%2Fwww.ams.org%2Fmathscinet-getitem%3Fmr%3D2445243&rft.isbn=978-0-19-921986-5&rft.aulast=Hardy&rft.aufirst=G.+H.&rft.au=Wright%2C+E.+M.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFundamental+theorem+of+arithmetic" class="Z3988"></span><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r886058088"/></li>
<li><cite id="CITEREFA._KornilowiczP._Rudnicki2004" class="citation">A. Kornilowicz; P. Rudnicki (2004), "Fundamental theorem of arithmetic", <i><a href="/w/index.php?title=Formalized_Mathematics&action=edit&redlink=1" class="new" title="Formalized Mathematics (page does not exist)">Formalized Mathematics</a></i>, <b>12</b> (2): 179–185</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Formalized+Mathematics&rft.atitle=Fundamental+theorem+of+arithmetic&rft.volume=12&rft.issue=2&rft.pages=179-185&rft.date=2004&rft.au=A.+Kornilowicz&rft.au=P.+Rudnicki&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFundamental+theorem+of+arithmetic" class="Z3988"></span><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r886058088"/></li>
<li><cite id="CITEREFLong1972" class="citation">Long, Calvin T. (1972), <i>Elementary Introduction to Number Theory</i> (2nd ed.), Lexington: <a href="/wiki/D._C._Heath_and_Company" title="D. C. Heath and Company">D. C. Heath and Company</a>, <a href="/wiki/Library_of_Congress_Control_Number" title="Library of Congress Control Number">LCCN</a> <a rel="nofollow" class="external text" href="//lccn.loc.gov/77-171950">77-171950</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Elementary+Introduction+to+Number+Theory&rft.place=Lexington&rft.edition=2nd&rft.pub=D.+C.+Heath+and+Company&rft.date=1972&rft_id=info%3Alccn%2F77-171950&rft.aulast=Long&rft.aufirst=Calvin+T.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFundamental+theorem+of+arithmetic" class="Z3988"></span><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r886058088"/>.</li>
<li><cite id="CITEREFPettofrezzoByrkit1970" class="citation">Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), <i>Elements of Number Theory</i>, Englewood Cliffs: <a href="/wiki/Prentice_Hall" title="Prentice Hall">Prentice Hall</a>, <a href="/wiki/Library_of_Congress_Control_Number" title="Library of Congress Control Number">LCCN</a> <a rel="nofollow" class="external text" href="//lccn.loc.gov/77-81766">77-81766</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Elements+of+Number+Theory&rft.place=Englewood+Cliffs&rft.pub=Prentice+Hall&rft.date=1970&rft_id=info%3Alccn%2F77-81766&rft.aulast=Pettofrezzo&rft.aufirst=Anthony+J.&rft.au=Byrkit%2C+Donald+R.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFundamental+theorem+of+arithmetic" class="Z3988"></span><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r886058088"/>.</li>
<li><cite id="CITEREFRiesel1994" class="citation">Riesel, Hans (1994), <i>Prime Numbers and Computer Methods for Factorization (second edition)</i>, Boston: Birkhäuser, <a href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> <a href="/wiki/Special:BookSources/0-8176-3743-5" title="Special:BookSources/0-8176-3743-5"><bdi>0-8176-3743-5</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Prime+Numbers+and+Computer+Methods+for+Factorization+%28second+edition%29&rft.place=Boston&rft.pub=Birkh%C3%A4user&rft.date=1994&rft.isbn=0-8176-3743-5&rft.aulast=Riesel&rft.aufirst=Hans&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFundamental+theorem+of+arithmetic" class="Z3988"></span><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r886058088"/></li>
<li><cite id="CITEREFWeil2007" class="citation book">Weil, André (2007) [1984]. <i><a href="/wiki/Number_Theory:_An_Approach_through_History_from_Hammurapi_to_Legendre" title="Number Theory: An Approach through History from Hammurapi to Legendre">Number Theory: An Approach through History from Hammurapi to Legendre</a></i>. Modern Birkhäuser Classics. Boston, MA: Birkhäuser. <a href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> <a href="/wiki/Special:BookSources/978-0-817-64565-6" title="Special:BookSources/978-0-817-64565-6"><bdi>978-0-817-64565-6</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Number+Theory%3A+An+Approach+through+History+from+Hammurapi+to+Legendre&rft.place=Boston%2C+MA&rft.series=Modern+Birkh%C3%A4user+Classics&rft.pub=Birkh%C3%A4user&rft.date=2007&rft.isbn=978-0-817-64565-6&rft.aulast=Weil&rft.aufirst=Andr%C3%A9&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFundamental+theorem+of+arithmetic" class="Z3988"></span><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r886058088"/></li>
<li><span class="citation mathworld" id="Reference-Mathworld-Abnormal_number"><cite class="citation web"><a href="/wiki/Eric_W._Weisstein" title="Eric W. Weisstein">Weisstein, Eric W.</a> <a rel="nofollow" class="external text" href="http://mathworld.wolfram.com/AbnormalNumber.html">"Abnormal number"</a>. <i><a href="/wiki/MathWorld" title="MathWorld">MathWorld</a></i>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=MathWorld&rft.atitle=Abnormal+number&rft.au=Weisstein%2C+Eric+W.&rft_id=http%3A%2F%2Fmathworld.wolfram.com%2FAbnormalNumber.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFundamental+theorem+of+arithmetic" class="Z3988"></span><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r886058088"/></span></li>
<li><span class="citation mathworld" id="Reference-Mathworld-Fundamental_Theorem_of_Arithmetic"><cite class="citation web"><a href="/wiki/Eric_W._Weisstein" title="Eric W. Weisstein">Weisstein, Eric W.</a> <a rel="nofollow" class="external text" href="http://mathworld.wolfram.com/FundamentalTheoremofArithmetic.html">"Fundamental Theorem of Arithmetic"</a>. <i><a href="/wiki/MathWorld" title="MathWorld">MathWorld</a></i>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=MathWorld&rft.atitle=Fundamental+Theorem+of+Arithmetic&rft.au=Weisstein%2C+Eric+W.&rft_id=http%3A%2F%2Fmathworld.wolfram.com%2FFundamentalTheoremofArithmetic.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFundamental+theorem+of+arithmetic" class="Z3988"></span><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r886058088"/></span></li></ul>
<h2><span class="mw-headline" id="External_links">External links</span><span class="mw-editsection"><a href="/w/index.php?title=Special:Badtitle/dummy_title_for_API_calls_set_in_api.php&action=edit&section=14" title="Edit section: External links" data-section="14" class="mw-ui-icon mw-ui-icon-element mw-ui-icon-minerva-edit-enabled edit-page">Edit</a></span></h2>
<ul><li><a rel="nofollow" class="external text" href="https://gowers.wordpress.com/2011/11/13/why-isnt-the-fundamental-theorem-of-arithmetic-obvious">Why isn’t the fundamental theorem of arithmetic obvious?</a></li>
<li><a rel="nofollow" class="external text" href="http://www.cut-the-knot.org/blue/gcd_fta.shtml">GCD and the Fundamental Theorem of Arithmetic</a> at <a href="/wiki/Cut-the-knot" class="mw-redirect" title="Cut-the-knot">cut-the-knot</a>.</li>
<li><a rel="nofollow" class="external text" href="http://planetmath.org/fundamentaltheoremofarithmeticproofofthe">PlanetMath: Proof of fundamental theorem of arithmetic</a></li>
<li><a rel="nofollow" class="external text" href="http://fermatslasttheorem.blogspot.com/2005/06/unique-factorization.html">Fermat's Last Theorem Blog: Unique Factorization</a>, a blog that covers the history of <a href="/wiki/Fermat%27s_Last_Theorem" title="Fermat's Last Theorem">Fermat's Last Theorem</a> from <a href="/wiki/Diophantus_of_Alexandria" class="mw-redirect" title="Diophantus of Alexandria">Diophantus of Alexandria</a> to the proof by <a href="/wiki/Andrew_Wiles" title="Andrew Wiles">Andrew Wiles</a>.</li>
<li><a rel="nofollow" class="external text" href="http://demonstrations.wolfram.com/FundamentalTheoremOfArithmetic/">"Fundamental Theorem of Arithmetic"</a> by Hector Zenil, <a href="/wiki/Wolfram_Demonstrations_Project" title="Wolfram Demonstrations Project">Wolfram Demonstrations Project</a>, 2007.</li>
<li><cite class="citation web">Grime, James. <a rel="nofollow" class="external text" href="http://www.numberphile.com/videos/1notprime.html">"1 and Prime Numbers"</a>. <i>Numberphile</i>. <a href="/wiki/Brady_Haran" title="Brady Haran">Brady Haran</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=Numberphile&rft.atitle=1+and+Prime+Numbers&rft.aulast=Grime&rft.aufirst=James&rft_id=http%3A%2F%2Fwww.numberphile.com%2Fvideos%2F1notprime.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFundamental+theorem+of+arithmetic" class="Z3988"></span><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r886058088"/></li></ul>
<div role="navigation" class="navbox" aria-labelledby="Fundamental_mathematical_theorems" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div class="plainlinks hlist navbar mini"><ul><li class="nv-view"><a href="/wiki/Template:Fundamental_theorems" title="Template:Fundamental theorems"><abbr title="View this template" style=";;background:none transparent;border:none;-moz-box-shadow:none;-webkit-box-shadow:none;box-shadow:none; padding:0;">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Fundamental_theorems" title="Template talk:Fundamental theorems"><abbr title="Discuss this template" style=";;background:none transparent;border:none;-moz-box-shadow:none;-webkit-box-shadow:none;box-shadow:none; padding:0;">t</abbr></a></li><li class="nv-edit"><a class="external text" href="/w/index.php?title=Template:Fundamental_theorems&action=edit"><abbr title="Edit this template" style=";;background:none transparent;border:none;-moz-box-shadow:none;-webkit-box-shadow:none;box-shadow:none; padding:0;">e</abbr></a></li></ul></div><div id="Fundamental_mathematical_theorems" style="font-size:114%;margin:0 4em"><a href="/wiki/Fundamental_theorem" title="Fundamental theorem">Fundamental mathematical theorems</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0px;height:2.5em;"><div style="padding:0em 0.25em">
<ul><li><a class="mw-selflink selflink">Arithmetic</a></li>
<li><a href="/wiki/Fundamental_theorem_of_algebra" title="Fundamental theorem of algebra">Algebra</a></li>
<li><a href="/wiki/Fundamental_theorem_of_calculus" title="Fundamental theorem of calculus">Calculus</a></li>
<li>Geometry
<ul><li><a href="/wiki/Fundamental_theorem_of_curves" title="Fundamental theorem of curves">Curves</a></li>
<li><a href="/wiki/Collineation" title="Collineation">Projective</a></li>
<li><a href="/wiki/Fundamental_theorem_of_Riemannian_geometry" title="Fundamental theorem of Riemannian geometry">Riemannian</a></li></ul></li>
<li>Groups
<ul><li><a href="/wiki/Fundamental_theorem_of_cyclic_groups" class="mw-redirect" title="Fundamental theorem of cyclic groups">Cyclic</a></li>
<li><a href="/wiki/Fundamental_theorem_of_finitely_generated_abelian_groups" class="mw-redirect" title="Fundamental theorem of finitely generated abelian groups">Finitely generated Abelian</a></li></ul></li>
<li><a href="/wiki/Fundamental_theorem_of_linear_algebra" title="Fundamental theorem of linear algebra">Linear algebra</a></li>
<li><a href="/wiki/Fundamental_theorem_of_linear_programming" title="Fundamental theorem of linear programming">Linear programming</a></li>
<li><a href="/wiki/Fundamental_lemma_of_calculus_of_variations" title="Fundamental lemma of calculus of variations">Calculus of variations</a></li>
<li><a href="/wiki/Helmholtz_decomposition" title="Helmholtz decomposition">Vector analysis</a></li>
<li><a href="/wiki/Fundamental_theorem_on_homomorphisms" title="Fundamental theorem on homomorphisms">Homomorphisms</a></li>
<li><a href="/wiki/Fundamental_theorem_of_Galois_theory" title="Fundamental theorem of Galois theory">Galois theory</a></li></ul>
</div></td></tr></tbody></table></div>
<div role="navigation" class="navbox" aria-labelledby="Divisibility-based_sets_of_integers" style="padding:3px"><table class="nowraplinks mw-collapsible mw-collapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="3"><div class="plainlinks hlist navbar mini"><ul><li class="nv-view"><a href="/wiki/Template:Divisor_classes" title="Template:Divisor classes"><abbr title="View this template" style=";;background:none transparent;border:none;-moz-box-shadow:none;-webkit-box-shadow:none;box-shadow:none; padding:0;">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Divisor_classes" title="Template talk:Divisor classes"><abbr title="Discuss this template" style=";;background:none transparent;border:none;-moz-box-shadow:none;-webkit-box-shadow:none;box-shadow:none; padding:0;">t</abbr></a></li><li class="nv-edit"><a class="external text" href="/w/index.php?title=Template:Divisor_classes&action=edit"><abbr title="Edit this template" style=";;background:none transparent;border:none;-moz-box-shadow:none;-webkit-box-shadow:none;box-shadow:none; padding:0;">e</abbr></a></li></ul></div><div id="Divisibility-based_sets_of_integers" style="font-size:114%;margin:0 4em">Divisibility-based sets of integers</div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Overview</th><td class="navbox-list navbox-odd hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em">
<ul><li><a href="/wiki/Integer_factorization" title="Integer factorization">Integer factorization</a></li>
<li><a href="/wiki/Divisor" title="Divisor">Divisor</a></li>
<li><a href="/wiki/Unitary_divisor" title="Unitary divisor">Unitary divisor</a></li>
<li><a href="/wiki/Divisor_function" title="Divisor function">Divisor function</a></li>
<li><a href="/wiki/Prime_factor" class="mw-redirect" title="Prime factor">Prime factor</a></li>
<li><a class="mw-selflink selflink">Fundamental theorem of arithmetic</a></li>
<li><a href="/wiki/Arithmetic_number" title="Arithmetic number">Arithmetic number</a></li></ul>
</div></td><td class="navbox-image" rowspan="6" style="width:1px;padding:0px 0px 0px 2px"><div><a href="/wiki/File:Lattice_of_the_divisibility_of_60.svg" class="image" title="Divisibility of 60"><img alt="Divisibility of 60" src="/media/wikipedia/commons/thumb/5/51/Lattice_of_the_divisibility_of_60.svg/175px-Lattice_of_the_divisibility_of_60.svg.png" decoding="async" width="175" height="140" srcset="/media/wikipedia/commons/thumb/5/51/Lattice_of_the_divisibility_of_60.svg/263px-Lattice_of_the_divisibility_of_60.svg.png 1.5x, /media/wikipedia/commons/thumb/5/51/Lattice_of_the_divisibility_of_60.svg/350px-Lattice_of_the_divisibility_of_60.svg.png 2x" data-file-width="313" data-file-height="250" /></a></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Factorization forms</th><td class="navbox-list navbox-even hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em">
<ul><li><a href="/wiki/Prime_number" title="Prime number">Prime</a></li>
<li><a href="/wiki/Composite_number" title="Composite number">Composite</a></li>
<li><a href="/wiki/Semiprime" title="Semiprime">Semiprime</a></li>
<li><a href="/wiki/Pronic_number" title="Pronic number">Pronic</a></li>
<li><a href="/wiki/Sphenic_number" title="Sphenic number">Sphenic</a></li>
<li><a href="/wiki/Square-free_integer" title="Square-free integer">Square-free</a></li>
<li><a href="/wiki/Powerful_number" title="Powerful number">Powerful</a></li>
<li><a href="/wiki/Perfect_power" title="Perfect power">Perfect power</a></li>
<li><a href="/wiki/Achilles_number" title="Achilles number">Achilles</a></li>
<li><a href="/wiki/Smooth_number" title="Smooth number">Smooth</a></li>
<li><a href="/wiki/Regular_number" title="Regular number">Regular</a></li>
<li><a href="/wiki/Rough_number" title="Rough number">Rough</a></li>
<li><a href="/wiki/Unusual_number" title="Unusual number">Unusual</a></li></ul>
</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Constrained divisor sums</th><td class="navbox-list navbox-odd hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em">
<ul><li><a href="/wiki/Perfect_number" title="Perfect number">Perfect</a></li>
<li><a href="/wiki/Almost_perfect_number" title="Almost perfect number">Almost perfect</a></li>
<li><a href="/wiki/Quasiperfect_number" title="Quasiperfect number">Quasiperfect</a></li>
<li><a href="/wiki/Multiply_perfect_number" title="Multiply perfect number">Multiply perfect</a></li>
<li><a href="/wiki/Hemiperfect_number" title="Hemiperfect number">Hemiperfect</a></li>
<li><a href="/wiki/Hyperperfect_number" title="Hyperperfect number">Hyperperfect</a></li>
<li><a href="/wiki/Superperfect_number" title="Superperfect number">Superperfect</a></li>
<li><a href="/wiki/Unitary_perfect_number" title="Unitary perfect number">Unitary perfect</a></li>
<li><a href="/wiki/Semiperfect_number" title="Semiperfect number">Semiperfect</a></li>
<li><a href="/wiki/Practical_number" title="Practical number">Practical</a></li>
<li><a href="/wiki/Erd%C5%91s%E2%80%93Nicolas_number" title="Erdős–Nicolas number">Erdős–Nicolas</a></li></ul>
</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">With many divisors</th><td class="navbox-list navbox-even hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em">
<ul><li><a href="/wiki/Abundant_number" title="Abundant number">Abundant</a></li>
<li><a href="/wiki/Primitive_abundant_number" title="Primitive abundant number">Primitive abundant</a></li>
<li><a href="/wiki/Highly_abundant_number" title="Highly abundant number">Highly abundant</a></li>
<li><a href="/wiki/Superabundant_number" title="Superabundant number">Superabundant</a></li>
<li><a href="/wiki/Colossally_abundant_number" title="Colossally abundant number">Colossally abundant</a></li>
<li><a href="/wiki/Highly_composite_number" title="Highly composite number">Highly composite</a></li>
<li><a href="/wiki/Superior_highly_composite_number" title="Superior highly composite number">Superior highly composite</a></li>
<li><a href="/wiki/Weird_number" title="Weird number">Weird</a></li></ul>
</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Aliquot_sequence" title="Aliquot sequence">Aliquot sequence</a>-related</th><td class="navbox-list navbox-odd hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em">
<ul><li><a href="/wiki/Untouchable_number" title="Untouchable number">Untouchable</a></li>
<li><a href="/wiki/Amicable_numbers" title="Amicable numbers">Amicable</a></li>
<li><a href="/wiki/Sociable_number" title="Sociable number">Sociable</a></li>
<li><a href="/wiki/Betrothed_numbers" title="Betrothed numbers">Betrothed</a></li></ul>
</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other sets</th><td class="navbox-list navbox-even hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em">
<ul><li><a href="/wiki/Deficient_number" title="Deficient number">Deficient</a></li>
<li><a href="/wiki/Friendly_number" title="Friendly number">Friendly</a></li>
<li><a href="/wiki/Friendly_number#Solitary_numbers" title="Friendly number">Solitary</a></li>
<li><a href="/wiki/Sublime_number" title="Sublime number">Sublime</a></li>
<li><a href="/wiki/Harmonic_divisor_number" title="Harmonic divisor number">Harmonic divisor</a></li>
<li><a href="/wiki/Frugal_number" title="Frugal number">Frugal</a></li>
<li><a href="/wiki/Equidigital_number" title="Equidigital number">Equidigital</a></li>
<li><a href="/wiki/Extravagant_number" title="Extravagant number">Extravagant</a></li></ul>
</div></td></tr></tbody></table></div>
<!--
NewPP limit report
Parsed by mw1341
Cached time: 20190911022005
Cache expiry: 2592000
Dynamic content: false
Complications: [vary‐revision‐sha1]
CPU time usage: 0.400 seconds
Real time usage: 0.645 seconds
Preprocessor visited node count: 1675/1000000
Preprocessor generated node count: 0/1500000
Post‐expand include size: 53840/2097152 bytes
Template argument size: 2758/2097152 bytes
Highest expansion depth: 11/40
Expensive parser function count: 3/500
Unstrip recursion depth: 0/20
Unstrip post‐expand size: 32579/5000000 bytes
Number of Wikibase entities loaded: 3/400
Lua time usage: 0.183/10.000 seconds
Lua memory usage: 4.69 MB/50 MB
-->
<!--
Transclusion expansion time report (%,ms,calls,template)
100.00% 441.932 1 -total
27.81% 122.889 10 Template:Citation
22.37% 98.841 1 Template:Reflist
20.67% 91.337 4 Template:Quotation
9.72% 42.953 4 Template:Comma_separated_entries
9.65% 42.628 2 Template:Broken_ref
9.64% 42.592 2 Template:Cite_book
9.32% 41.186 1 Template:Hardy_and_Wright
5.91% 26.105 4 Template:Trim_quotes
5.15% 22.753 12 Template:If_empty
-->
</div>' |
