# User:Virginia-American/Sandbox/Fundamental theorem of arithmetic

In number theory, the fundamental theorem of arithmetic (also called the unique factorization theorem or the unique-prime-factorization theorem) states (existence) that every integer greater than 1 is either prime itself or is the product of prime numbers, and (uniqueness) that, although the order of the primes in the second case is arbitrary, the primes themselves are not.[1][2][3] For example,

${\displaystyle 1200=2^{4}\times 3^{1}\times 5^{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=\cdots {\text{ etc.}}\!}$

The content of the theorem is that in any representation of 1200 as a product of primes, there will always be four 2s, one 3, and two 5s.

## Classification of integers

To clarify the role of the integer 1, and to prepare for more general settings than the integers, it is useful to classify the integers using terminology from abstract algebra, specifically from algebraic number theory and ring theory:[4]

zero 0
positive integers 1, 2, 3, ...
negative integers ..., −3, −2, −1
units −1 and 1
prime numbers ..., −3, −2, 2, 3, 5, ...
composite numbers ..., −6, −4, 4, 6, 8, 9, ...

Using it we have:

"A nonzero integer is either positive or negative."
"A negative integer is the unit −1 times a positive integer."
"A positive integer is either the unit 1, a positive prime, or the product of positive primes.
Up to the order of the factors, this product is uniquely determined by the integer."



To avoid constantly repeating the special cases, the definition of "product" can be slightly expanded to include as "products" the two cases in wheich there is no actual multiplication: the empty product with no factors and the "product" with only one factor. Under this convention the theorem reads:

"Every positive integer is the product of positive primes, and, except for the order of the factors,
in one way only. The integer 1 is the empty product of no primes."


## History

Book VII, propositions 30 and 32 of Euclid's Elements is essentially the statement and proof of the fundamental theorem. Article 16 of Gauss' Disquisitiones Arithmeticae is an early modern statement and proof employing modular arithmetic.

## Applications

### Canonical representation of a positive integer

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

${\displaystyle n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{k}^{\alpha _{k}}=\prod _{i=1}^{k}p_{i}^{\alpha _{i}}}$

where p1 < p2 < ... < pk are primes and the αi are positive integers.

This representation is called the canonical representation[5] of n, or the standard form[6] of n.
E.g., 12 = 22·3, 1296 = 24·34, and 220 = 22·5·11.

Note that factors p0 = 1 may be inserted without changing the value of n. In fact, any integer can be uniquely represented as an infinite product taken over all the prime numbers,

${\displaystyle n=2^{n_{2}}3^{n_{3}}5^{n_{5}}7^{n_{7}}\cdots =\prod p_{i}^{n_{p_{i}}}.}$

where all but a finite number of the ni are zero.

### Arithmetic operations

This representation is convenient for expressions like these for the product, gcd, and lcm:

${\displaystyle a\cdot b=2^{a_{2}+b_{2}}\,3^{a_{3}+b_{3}}\,5^{a_{5}+b_{5}}\,7^{a_{7}+b_{7}}\cdots =\prod p_{i}^{a_{p_{i}}+b_{p_{i}}},}$
${\displaystyle \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}})},}$
${\displaystyle \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}})}.}$

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

### Arithmetical functions

Many arithmetical functions are defined using the canonical representation. In particular, the values of additive and multiplicative functions are determined by their values on the powers of prime numbers.

## Proof

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

### Existence

By inspection, the small natural numbers 1, 2, 3, 4, ... are the product of primes. This is the basis for a proof by induction. Assume it is true for all numbers less than n. If n is prime, there is nothing more to prove. Otherwise, there are integers a and b, where n = ab and 1 < ab < n. By the induction hypothesis, a = p1p2...pn and b = q1q2...qm are products of primes. But then n = ab = p1p2...pnq1q2...qm is also.

### Uniqueness

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

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

We must show m = n and that the qj are a rearrangement of the pi.

By Euclid's lemma p1 must divide one of the qj; relabeling the qj if necessary, say that p1 divides q1. But q1 is prime, so its only divisors are itself and 1. Therefore, p1 = q1, so that

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

Reasoning the same way, p2 must equal one of the remaining qj. Relabeling again if necessary, say p2 = q2. Then

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

This can be done for all m of the pi, showing that mn. If there were any qj left over we would have

{\displaystyle {\begin{aligned}{\frac {s}{p_{1}p_{2}\cdots p_{m}}}&=1\\&=q_{k}\cdots q_{n},\end{aligned}}}

a contradiction, since the product of numbers greater than 1 cannot equal 1. Therefore m = n and every qj is a pi.

## Generalizations

The first generalization of the theorem is found in Gauss's second monograph on biquadratic reciprocity. This paper introduced what is now denoted ${\displaystyle \mathbb {Z} [i]}$, where ${\displaystyle i^{2}=-1.}$ This is the ring of Gaussian integers, and is the set of all complex numbers a + bi where a and b are integers. Gauss 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.[7]

Similarly, Eisenstein introduced the ring ${\displaystyle \mathbb {Z} [\omega ]}$, where ${\displaystyle \omega ={\frac {-1+{\sqrt {-3}}}{2}},}$   ${\displaystyle \omega ^{3}=1.}$ This is the ring of Eisenstein integers, and Eisenstein proved its units are the six numbers ${\displaystyle \pm 1,\pm \omega ,\pm \omega ^{2}}$ and that it has unique factorization.

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

${\displaystyle 6=2\times 3=(1+{\sqrt {-5}})\times (1-{\sqrt {-5}}),}$

and all of factors can be proven prme in that ring.[8]

In algebraic number theory, and more generally in ring theory, a unique factorization domain is defined as an algebraic structure in which the fundamental theorem of arithmetic holds. For example, any Euclidean domain or principal ideal domain can be proven to be a unique factorization domain.

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

## Notes

1. ^ Long (1972, p. 44)
2. ^ Pettofrezzo & Byrkit (1970, p. 53)
3. ^ Hardy & Wright, Thm 2
4. ^ Riesel, p. 1
5. ^ Long (1972, p. 45)
6. ^ Pettofrezzo & Byrkit (1970, p. 55)
7. ^ Gauss, BQ, §§ 31–34
8. ^ Hardy & Wright, § 14.6

## References

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

• Gauss, Carl Friedrich; Clarke, Arthur A. (translator into English) (1986), Disquisitiones Arithemeticae (Second, corrected edition), New York: Springer, ISBN 0387962549
• Gauss, Carl Friedrich; Maser, H. (translator into German) (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition), New York: Chelsea, ISBN 0-8284-0191-8

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

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

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

• Baker, Alan (1984), A Concise Introduction to the Theory of Numbers, Cambridge, UK: Cambridge University Press, ISBN 978-0-521-28654-1
• Hardy, G. H.; Wright, E. M. (1979), An Introduction to the Theory of Numbers (fifth ed.), USA: Oxford University Press, ISBN 978-0-19-853171-5
• A. Kornilowicz and P. Rudnicki. Fundamental theorem of arithmetic. Formalized Mathematics, 12(2):179–185, 2004.
• Long, Calvin T. (1972), Elementary Introduction to Number Theory (2nd ed.), Lexington: D. C. Heath and Company.
• Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elements of Number Theory, Englewood Cliffs: Prentice Hall.
• Riesel, Hans (1994), Prime Numbers and Computer Methods for Factorization (second edition), Boston: Birkhäuser, ISBN 0-8176-3743-5