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

Not to be confused with Fundamental theorem of algebra or Fundamental theorem of calculus.

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. For example,

$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:

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:

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

where p₁ < p₂ < ... < p_k are primes and the α_i are positive integers.

This representation is called the canonical representation of n, or the standard form of n.
E.g., 12 = 2²·3, 1296 = 2⁴·3⁴, and 220 = 2²·5·11.

Note that factors p⁰ = 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,

$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 n_i are zero.

Arithmetic operations

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

$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}}},$

$\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}})},$

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

Main article: Arithmetic function

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 < a ≤ b < n. By the induction hypothesis, a = p₁p₂...p_n and b = q₁q₂...q_m are products of primes. But then n = ab = p₁p₂...p_nq₁q₂...q_m is also.

Uniqueness

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

${\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 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

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

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

${\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 p_i, showing that m ≤ n. If there were any q_j left over we would have

${\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 q_j is a p_i.

Generalizations

The first generalization of the theorem is found in Gauss's second monograph on biquadratic reciprocity. This paper introduced what is now denoted $\mathbb {Z} [i]$, where $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.

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

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

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

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

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.

See also

• Euler product formula
• Integer factorization
• Prime signature

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 {{citation}}: |first2= has generic name (help)

• 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 {{citation}}: |first2= has generic name (help)

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

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

External links

• GCD and the Fundamental Theorem of Arithmetic at cut-the-knot
• PlanetMath: Proof of fundamental theorem of arithmetic
• Fermat's Last Theorem Blog: Unique Factorization, A blog that covers the history of Fermat's Last Theorem from Diophantus of Alexandria to the proof by Andrew Wiles.
• "Fundamental Theorem of Arithmetic" by Hector Zenil, Wolfram Demonstrations Project, 2007.