Fundamental theorem of arithmetic: Difference between revisions

Revision as of 12:25, 28 April 2014

Latest revision as of 07:24, 1 August 2025

(367 intermediate revisions by more than 100 users not shown)

Line 1:

{{short description|Integers have unique prime factorizations}}

{{Distinguish|Fundamental theorem of algebra}}

{{about|the unique factorization of integers into prime numbers|the theorem about roots of a polynomial|Fundamental theorem of algebra|other fundamental theorems|List of theorems called fundamental}}

[[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 ''DA'', Gauss referred to the fundamental theorem as the [[law of quadratic reciprocity]].<ref>{{Harvtxt|Gauss|Clarke|1986|loc=Art. 131}}</ref>]]

[[File:Disqvisitiones-800.jpg|thumb|In ''[[Disquisitiones Arithmeticae]]'' (1801) [[Carl Friedrich Gauss|Gauss]] proved the unique factorization theorem<ref name="Gauss1801.loc=16">{{Harvtxt|Gauss|1986|loc=Art. 16}}</ref> and used it to prove the [[law of quadratic reciprocity]].<ref>{{Harvtxt|Gauss|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>Under the [[empty product|empty product rule]] the theorem reduces to: every positive integer has unique prime factorization.</ref> either is prime itself or is the product of [[prime number]]s, and that, although the order of the primes in the second case is arbitrary, the primes themselves are not.<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,

In [[mathematics]], the '''fundamental theorem of arithmetic''', also called the '''unique factorization theorem''' and '''prime factorization theorem''', states that every [[integer]] greater than 1 is prime or can be represented uniquely as a product of [[prime number]]s, [[up to]] the order of the factors.{{efn|Using the standard conventions for the [[product of a sequence]] (the value of the [[empty product]] is {{val|1}} and the product of a single factor is the factor itself), the theorem is often stated as: ''every positive integer can be represented uniquely as a product of prime numbers, up to the order of the factors''.}}<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,

:<math>

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

</math>

The theorem says two things about 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

1200 = 2{{sup|4}} &times; 3{{sup|1}} &times; 5{{sup|2}} = 3 &times; 2&times; 2&times; 2&times; 2 &times; 5 &times; 5 = 5 &times; 2&times; 3&times; 2&times; 5 &times; 2 &times; 2 = etc.

(for example, <math>12 = 2 \cdot 6 = 3 \cdot 4</math>).

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, <math>2 = 2 \cdot 1 = 2 \cdot 1 \cdot 1 = \ldots</math>

The theorem is stating two things: first, that 1200 ''can'' be represented as a product of primes, and second, no matter how this is done, there will always be four 2s, one 3, two 5s, and no other primes in the product.

The theorem generalizes to other [[algebraic structure]]s that are called [[unique factorization ___domain]]s and include [[principal ideal ___domain]]s, [[Euclidean ___domain]]s, and [[polynomial ring]]s over a [[field (mathematics)|field]]. However, the theorem does not hold for [[algebraic integer]]s.{{efn|In a [[ring of algebraic integers]], the factorization into prime elements may be non unique, but one can recover a unique factorization if one factors into [[ideal (ring theory)|ideal]]s.}} This failure of unique factorization is one of the reasons for the difficulty of the proof of [[Fermat's Last Theorem]]. The implicit use of unique factorization in rings of algebraic integers is behind the error of many of the numerous false proofs that have been written during the 358 years between [[Pierre de Fermat|Fermat's]] statement and [[Wiles's proof of Fermat's Last Theorem|Wiles's proof]].

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).

==History==

Book VII, propositions 30 and 32 of [[Euclid]]'s [[Euclid's Elements|Elements]] is essentially the statement and proof of the fundamental theorem.

The fundamental theorem can be derived from Book VII, propositions 30, 31 and 32, and Book IX, proposition 14 of [[Euclid]]'s ''[[Euclid's Elements|Elements]]''.

{{Quotation|

If two numbers by multiplying one another make some

Line 18 ⟶ 25:

|Euclid|[[#CITEREFEuclidHeath1956|Elements Book VII]], Proposition 30}}

The(In propositionmodern 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]]. , Andand it is the key in the proof of the fundamental theorem of arithmetic.

{{Quotation|

Line 24 ⟶ 31:

|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]].

The proposition 31 is derived from the proposition 30.

{{Quotation|

Line 30 ⟶ 37:

|Euclid|[[#CITEREFEuclidHeath1956|Elements Book VII]], Proposition 32}}

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

{{Quotation|

Article 16 of [[Carl Friedrich Gauss|Gauss]]' ''[[Disquisitiones Arithmeticae]]'' is an early modern statement and proof employing [[modular arithmetic]].<ref name="Gauss1801.loc=16" />

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]].{{efn|{{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."}} Indeed, in this proposition the exponents are all equal to one, so nothing is said for the general case.

While [[Euclid]] took the first step on the way to the existence of prime factorization, [[Kamāl al-Dīn al-Fārisī]] took the final step{{efn|{{Cite journal |last=A. Goksel Agargun and E. Mehmet Özkan |title=A Historical Survey of the Fundamental Theorem of Arithmetic |url=https://core.ac.uk/download/pdf/82721726.pdf |journal=Historia Mathematica |pages=209|quote=One could say that Euclid takes the first step on the way to the existence of prime factorization, and al-Farisi takes the final step by actually proving the existence of a finite prime factorization in his first proposition.}}}} and stated for the first time the fundamental theorem of arithmetic.{{efn|{{Cite book|url=https://books.google.com/books?id=7veIAgAAQBAJ&q=fundamental+theorem+of+arithmetic+discovered+al-farisi&pg=PA385|title=Encyclopedia of the History of Arabic Science|last=Rashed|first=Roshdi|date=2002-09-11|publisher=Routledge|isbn=9781134977246|language=en|page=385|quote=The famous physicist and mathematician Kamal al-Din al-Farisi compiled a paper in which he set out deliberately to prove the theorem of Ibn Qurra in an algebraic way. This forced him to an understanding of the first arithmetical functions and to a full preparation which led him to state for the first time the fundamental theorem of arithmetic.}}}}

Article 16 of [[Carl Friedrich Gauss|Gauss]]'s ''[[Disquisitiones Arithmeticae]]'' seems to be the first proof of the uniqueness part of the theorem.<ref name="Gauss1801.loc=16" />

==Applications==

===Canonical representation of a positive integer=== <!-- Redirect [[Canonical form]] links here -->

Every positive integer {{math|''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}

n

= \prod_{i=1}^{k} p_i^{n_i},

= p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_k^{\alpha_k}

= \prod_{i=1}^{k}p_i^{\alpha_i}

</math>

where {{nowrap begin}}math|''p''₁ < ''p''₂ < ... < ''p''_k{{nowrap end}} are primes and the α{{math|''n''_''i''}} are positive integers. This representation is commonly extended to all positive integers, including 1, by the convention that the [[empty product]] is equal to 1 (the empty product corresponds to {{math|1=''k'' = 0}}).

This representation is called the '''canonical representation'''<ref>{{harvtxt|Long|1972|p=45}}</ref> of {{math|''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,

:For example 999 = 3³×37,
:1000 = 2³×5³,
:1001 = 7×11×13.

Note that factorsFactors {{math|1=''p''⁰ = 1}} may be inserted without changing the value of {{math|''n''}} (e.g.for example, {{math|1=1000 = 2³×3⁰×5³}}).<br> In fact, any positive integer can be uniquely represented as an [[infinite product]] taken over all the positive prime numbers, as

:<math>n=2^{n_1}3^{n_2}5^{n_3}7^{n_4}\cdots=\prod_{i=1}^\infty p_i^{n_i},</math>

:<math>

where a finite number of the {{math|''n''_''i''}} are positive integers, and the others are zero.

n=2^{n_2}3^{n_3}5^{n_5}7^{n_7}\cdots=\prod p_i^{n_{p_i}}.

</math>

where a finite number of the ''n''_''i'' are positive integers, and the rest are zero. Allowing negative exponents provides a canonical form for positive [[rational number]]s.

===Arithmetic operations===

ThisThe representationcanonical isrepresentations convenient for expressions like these forof the product, [[greatest common divisor|gcd]] (GCD), and [[least common multiple|lcm]] (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

a\cdot b

&& = \prod p_i^{a_i+b_i},\\

=2^{a_2+b_2}\,3^{a_3+b_3}\,5^{a_5+b_5}\,7^{a_7+b_7}\cdots

\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^{a_{p_i}+b_{p_i}},

&& = \prod p_i^{\min(a_i,b_i)},\\

</math>

\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.

:<math>

\gcd(a,b)

=2^{\min(a_2,b_2)}\,3^{\min(a_3,b_3)}\,5^{\min(a_5,b_5)}\,7^{\min(a_7,b_7)}\cdots

=\prod p_i^{\min(a_{p_i},b_{p_i})},

</math>

===Arithmetic functions===

:<math>

{{Main article|Arithmetic function}}

\operatorname{lcm}(a,b)

=2^{\max(a_2,b_2)}\,3^{\max(a_3,b_3)}\,5^{\max(a_5,b_5)}\,7^{\max(a_7,b_7)}\cdots

=\prod p_i^{\max(a_{p_i},b_{p_i})}.

</math>

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.

While expressions like these are of great theoretical importance their practical use is limited by our ability to [[Integer factorization|factor]] numbers.

===Arithmetical functions===

{{Main|Arithmetic function}}

Many arithmetical 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): ifIf a prime ''p'' [[Divisor|divides]] the product of two [[natural number]]s ''a'' and ''b''integers, then ''p''it dividesmust ''a''divide orat ''p''least divides ''b'' (or both). That article has a proofone of Euclid'sthese lemma (in a nutshell: Euclid's lemma follows from [[Bézout's identity]] which in turn follows from [[extended Euclidean algorithm|Euclid's algorithm]]integers.)

===Existence===

It must be shown that every integer greater than {{math|1}} is either prime or a product of primes. First, {{math|2}} is prime, and this is true for {{tmath|1=n=2}}. Then, for {{tmath|n>2}}, assume by [[strong induction]], that this is true for all numbers greater than {{math|1}} and less than {{math|''n''}}. If {{math|''n''}} is prime, there is nothing more to prove. Otherwise, there are integers {{math|''a''}} and {{math|''b''}}, where {{math|1=''n'' = ''a b''}}, and {{math|1 < ''a'' ≤ ''b'' < ''n''}}. By the induction hypothesis, {{math|1=''a'' = ''p''₁ ''p''₂ ⋅⋅⋅ ''p''_''j''}} and {{math|1=''b'' = ''q''₁ ''q''₂ ⋅⋅⋅ ''q''_''k''}} are products of primes. But then {{math|1=''n'' = ''a b'' = ''p''₁ ''p''₂ ⋅⋅⋅ ''p''_''j'' ''q''₁ ''q''₂ ⋅⋅⋅ ''q''_''k''}} is a product of primes.

We need to show that every integer greater than 1 is a product of primes.

By induction: assume it is true for all numbers between 1 and ''n''. If ''n'' is prime, there is nothing more to prove (a prime is a trivial product of primes, a "product" with only one factor). Otherwise, there are integers ''a'' and ''b'', where ''n'' = ''ab'' and {{nowrap begin}}1 < ''a'' ≤ ''b'' < ''n''.{{nowrap end}}

By the induction hypothesis,

{{nowrap begin}}''a'' = ''p''₁''p''₂...''p''_''j''{{nowrap end}}

and

{{nowrap begin}}''b'' = ''q''₁''q''₂...''q''_''k''{{nowrap end}} are products of primes. But then

{{nowrap begin}}''n'' = ''ab'' = ''p''₁''p''₂...''p''_''j''''q''₁''q''₂...''q''_''k''{{nowrap end}} is a product of primes.

===Uniqueness===

Suppose, to the contrary, there is an integer that has two distinct prime factorizations. Let {{math|''n''}} be the least such integer and write {{math|1=''n'' = ''p''₁ ''p''₂ ... ''p''_''j'' = ''q''₁ ''q''₂ ... ''q''_''k''}}, where each {{math|''p''_''i''}} and {{math|''q''_''i''}} is prime. We see that {{math|''p''₁}} divides {{math|''q''₁ ''q''₂ ... ''q''_''k''}}, so {{math|''p''₁}} divides some {{math|''q''_''i''}} by [[Euclid's lemma]]. Without loss of generality, say {{math|''p''₁}} divides {{math|''q''₁}}. Since {{math|''p''₁}} and {{math|''q''₁}} are both prime, it follows that {{math|1=''p''₁ = ''q''₁}}. Returning to our factorizations of {{math|''n''}}, we may cancel these two factors to conclude that {{math|1=''p''₂ ... ''p''_''j'' = ''q''₂ ... ''q''_''k''}}. We now have two distinct prime factorizations of some integer strictly smaller than {{math|''n''}}, which contradicts the minimality of {{math|''n''}}.

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

===Uniqueness without Euclid's lemma===

:<math>

The fundamental theorem of arithmetic can also be proved without using Euclid's lemma.<ref>{{citation |last1=Dawson |first1=John W. |title=Why Prove it Again? Alternative Proofs in Mathematical Practice. |date=2015 |publisher=Springer |isbn=9783319173689 |page=45}}</ref> The proof that follows is inspired by Euclid's original version of the [[Euclidean algorithm]].

\begin{align}

s

&=p_1 p_2 \cdots p_m \\

&=q_1 q_2 \cdots q_n.

\end{align}

</math>

Assume that <math>s</math> is the smallest positive integer which is the product of prime numbers in two different ways. Incidentally, this implies that <math>s</math>, if it exists, must be a [[composite number]] greater than <math>1</math>. Now, say

We must show ''m'' = ''n'' and that the ''q''_''j'' are a rearrangement of the ''p''_''i''.

By [[Euclid's lemma]], ''p''₁ must divide one of the ''q''_''j''; relabeling the ''q''_''j'' if necessary, say that ''p''₁ divides ''q''₁. But ''q''₁ is prime, so its only divisors are itself and 1. Therefore, ''p''₁ = ''q''₁, so that

:<math>

\begin{align}

s

\frac{s}{p_1}

&=p_2 \cdots p_m \\

&=q_2 \cdots q_n.

\end{align}

</math>

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

:<math>

\begin{align}

\frac{s}{p_1 p_2}

&=p_3 \cdots p_m \\

&=q_3 \cdots q_n.

\end{align}

</math>

This can be done for each of the ''m'' ''p''_''i'''s, showing that ''m'' ≤ ''n'' and every ''p''_''i'' is a ''q''_''j''. Applying the same argument with the <math>p</math>'s and <math>q</math>'s reversed shows ''n'' ≤ ''m'' (hence ''m'' = ''n'') and every ''q''_''j'' is a ''p''_''i''.

===Elementary proof of uniqueness===

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

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

:<math>

\begin{align}

s

&=p_1 p_2 \cdots p_m \\

&=q_1 q_2 \cdots q_n.

Line 142 ⟶ 112:

</math>

Every <math>p_i</math> must be distinct from every <math>q_j.</math> Otherwise, if say <math>p_i=q_j,</math> then there would exist some positive integer <math>t=s/p_i=s/q_j</math> that is smaller than {{mvar|s}} and has two distinct prime factorizations. One may also suppose that <math>p_1 < q_1,</math> by exchanging the two factorizations, if needed.

If any ''p''_''i'' = ''q''_''j'' then, by cancellation, ''s''/''p''_''i'' = ''s''/''q''_''j'' would be a positive integer greater than 1 with two distinct factorizations. But ''s''/''p''_''i'' is smaller than ''s'', meaning ''s'' would not actually be the smallest such integer. Therefore every ''p''_''i'' must be distinct from every ''q''_''j''.

Setting <math>P=p_2\cdots p_m</math> and <math>Q=q_2\cdots q_n,</math> one has <math>s=p_1P=q_1Q.</math>

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

Also, since <math>p_1 < q_1,</math> one has <math>Q < P.</math>

It then follows that

:<math>s-p_1Q = (q_1-p_1)Q = p_1(P-Q) < s.</math>

As the positive integers less than {{mvar|s}} have been supposed to have a unique prime factorization, <math>p_1</math> must occur in the factorization of either <math>q_1-p_1</math> or {{mvar|Q}}. The latter case is impossible, as {{mvar|Q}}, being smaller than {{mvar|s}}, must have a unique prime factorization, and <math>p_1</math> differs from every <math>q_j.</math> The former case is also impossible, as, if <math>p_1</math> is a divisor of <math>q_1-p_1,</math> it must be also a divisor of <math>q_1,</math> which is impossible as <math>p_1</math> and <math>q_1</math> are distinct primes.

:<math>t = (q_1 - p_1)(q_2 \cdots q_n),</math>

Therefore, there cannot exist a smallest integer with more than a single distinct prime factorization. Every positive integer must either be a prime number itself, which would factor uniquely, or a composite that also factors uniquely into primes, or in the case of the integer <math>1</math>, not factor into any prime.

and note that 1 < ''q''₂ ≤ ''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''₂ ... ''p''_''m'') - (''q''₂ ... ''q''_''n'')) is positive, for if it were negative or zero then so would be its product with ''p''_''1'', but that product equals ''t'' which is positive. So ''u'' is either 1 or factors into primes. In either case, ''t'' = ''p''₁''u'' yields a prime factorization of ''t'', which we know to be unique, so ''p''₁ appears in the prime factorization of ''t''.

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

:<math>t = (r_1 \cdots r_h)(q_2 \cdots q_n),</math>

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

:<math>p_1(k+1) = q_1.</math>

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

==Generalizations==

{{more citations needed section|date=January 2024}}

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>

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 ([[up to]] the order and multiplication by units).<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 display="inline">\omega = \frac{-1 + \sqrt{-3}}{2}, </math> &nbsp; <math>\omega^3 =1 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 \timescdot 3 =

\left(1 + \sqrt{-5}\right)\timesleft(1 - \sqrt{-5}\right).

</math>

Examples like this caused the notion of "prime" to be modified. In <math>\mathbb{Z}\left[\sqrt{-5}\right]</math> it can be proven that if any of the factors above can be represented as a product, e.g.for example, 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; efor example, 2 divides neither (1 + <math>\sqrt{-5}</math>) nor (1 - <math>\sqrt{-5}</math>) even though it divides their product 6.g In [[algebraic number theory]] 2 is called [[irreducible element|irreducible]] in <math>\mathbb{Z}\left[\sqrt{-5}\right]</math> (only divisible by itself or a unit) but not [[prime element|prime]] in <math>\mathbb{Z}\left[\sqrt{-5}\right]</math> (if it divides a product it must divide one of the factors). The mention of <math>\mathbb{Z}\left[\sqrt{-5}\right]</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>

2 divides neither (1 + √−5) nor (1 − √−5) even though it divides their product 6. In [[algebraic number theory]] 2 is called '''irreducible''' (only divisible by itself or a unit) but not '''prime''' (if it divides a product it must divide one of the factors). Using these definitions it can be proven that in any ring a prime must be irreducible. Euclid's classical lemma can be rephrased as "in the ring of integers <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 wherein which factorization everyinto irreducibleirreducibles is primeessentially unique are called [[unique factorization ___domain]]s. AsImportant theexamples nameare indicates,[[polynomial thering]]s fundamentalover theoremthe ofintegers arithmeticor isover truea in them.[[field Important examples are(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.

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

==See also==

*[[Integer factorization]]

* [[Riemann zeta function#Euler product formula|Euler product formula]]

*[[List of theorems called fundamental]]

* [[Integer factorization]]

*[[Prime signature]], a characterization of how many primes divide a given number

* [[Noetherian ring]]

* [[Prime signature]]

==Notes==

{{reflistnotelist}}

==Citations==

{{reflist|30em}}

== References ==

{{sfn whitelist |CITEREFHardyWright2008}}

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

| last1last = Gauss | first1first = Carl Friedrich

| last2translator-last = Clarke | first2translator-first = Arthur A. (translator into English)

| title = Disquisitiones Arithemeticae (Second, corrected edition)

| publisher = [[Springer Science+Business Media|Springer]]

Line 210 ⟶ 168:

| year = 1986

| isbn = 978-0-387-96254-2

| url = httphttps://www.springer.com/mathematics/algebra/book/978-0-387-96254-2

}}

* {{citation

| last1last = Gauss | first1first = Carl Friedrich

| last2translator-last = Maser | first2translator-first = H. (translator into German)

| language = de

| title = Untersuchungen über hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition)

| publisher = Chelsea

Line 236 ⟶ 195:

These are in Gauss's ''Werke'', Vol II, pp.&nbsp;65–92 and 93–148; German translations are pp.&nbsp;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

| last2others = HeathTranslated | first2 =by [[Thomas L. (translator into English)Little Heath]]

| author2-link = Thomas Little Heath

| title = The thirteen books of the Elements

| edition = Second Edition Unabridged

Line 258 ⟶ 206:

| year = 1956

| isbn = 978-0-486-60089-5

| url = https://archive.org/details/thirteenbooksofe00eucl

| url = http://store.doverpublications.com/0486600890.html

| url-access = registration

}}

| ref = {{harvid|Euclid|Heath|1956}}

* {{Citation

}}

| last1=Hardy

* {{Hardy and Wright|mode=cs2}}

| first1=G. H.

| author1-link=G. H. Hardy

| last2=Wright

| first2=E. M.

| author2-link=E. M. Wright

| year=2008

| title=An Introduction to the Theory of Numbers

| edition=sixth

| place=USA

| publisher=Oxford University Press

| isbn=978-0-19-921986-5

| url=http://ukcatalogue.oup.com/product/9780199219865.do

}}

* {{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.

Line 312 ⟶ 238:

| year = 1994

| isbn = 0-8176-3743-5}}

* {{citation |last= Weil |first= André |year= 2007 |orig-year= 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 }}

* {{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 webcitation|last=Grime|first=James|title=1 and Prime Numbers|url=httphttps://www.numberphileyoutube.com/videoswatch?v=IQofiPqhJ_s| archive-url=https://1notprimeghostarchive.htmlorg/varchive/youtube/20211211/IQofiPqhJ_s| archive-date=2021-12-11 | url-status=live|work=Numberphile|date=3 February 2012 |publisher=[[Brady Haran]]}}{{cbignore}}

*[https://mindtested.com/posts/fundamental-theorem-of-arithmetic-real-numbers-chapter-1-class-10-mathematics-cbse-ncert Fundamental Theorem of Arithmetic ]

{{Fundamental theorems}}

{{Divisor classes}}

[[Category:Theorems about prime numbers]]

[[Category:Articles containing proofs]]

[[Category:FundamentalUniqueness theorems|Arithmetic]]

[[Category:factorization]]

[[de:Primfaktorzerlegung#Fundamentalsatz der Arithmetik]]