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.{{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 stepJOURNAL, A. Goksel Agargun and E. Mehmet Ãzkan, A Historical Survey of the Fundamental Theorem of Arithmetic,weblink Historia Mathematica, 209, One could say that Euclid takes the first step on the way to the existence of prime factorization, and al-Farisi takes the final step by actually proving the existence of a finite prime factorization in his first proposition., and stated for the first time the fundamental theorem of arithmetic.BOOK,weblink Encyclopedia of the History of Arabic Science, Rashed, Roshdi, 2002-09-11, Routledge, 9781134977246, en, 385, 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 Gauss' Disquisitiones Arithmeticae is an early modern statement and proof employing modular arithmetic.ApplicationsCanonical representation of a positive integer Every positive integer {{math|n > 1}} can be represented in exactly one way as a product of prime powers
n = p_1^{n_1}p_2^{n_2} cdots p_k^{n_k} prod_{i1}^{k} p_i^{n_i},where {{math|p1 | < p2 < ... < pk}} are primes and the {{math|ni}} 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{{harvtxt|Long|1972|p=45}} of {{math|n}}, or the standard form{{harvtxt|Pettofrezzo|Byrkit|1970|p=55}}{{Harvtxt|Hardy|Wright|2008|loc=§ 1.2}} of n. For example,
999 = 33Ã37,
1000 = 23Ã53,
1001 = 7Ã11Ã13.
Factors {{math|1=p0 = 1}} may be inserted without changing the value of {{math|n}} (for example, {{math|1=1000 = 23Ã30Ã53}}). In fact, any positive integer can be uniquely represented as an infinite product taken over all the positive prime numbers, as
n=2^{n_1}3^{n_2}5^{n_3}7^{n_4}cdots=prod_{i=1}^infty p_i^{n_i},
where a finite number of the {{math|ni}} are positive integers, and the others are zero. Allowing negative exponents provides a canonical form for positive rational numbers.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:
begin{alignat}{2}
acdot 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}
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
Many arithmetic 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 divides the product of two integers, then it must divide at least one of these 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. Then, by strong induction, assume 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 = p1 p2 â
â
â
p'j}} and {{math|1=b = q1 q2 â
â
â
q'k}} are products of primes. But then {{math|1=n = a b = p1 p2 â
â
â
p'j q1 q2 â
â
â
q'k}} 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 = p1 p2 ... p'j = q1 q2 ... q'k}}, where each {{math|p'i}} and {{math|q'i}} is prime. We see that {{math|p1}} divides {{math|q1 q2 ... q'k}}, so {{math|p1}} divides some {{math|q'i}} by Euclid's lemma. Without loss of generality, say {{math|p1}} divides {{math|q1}}. Since {{math|p1}} and {{math|q1}} are both prime, it follows that {{math|1=p1 = q1}}. Returning to our factorizations of {{math|n}}, we may cancel these two factors to conclude that {{math|1=p2 ... p'j = q2 ... q'k}}. We now have two distinct prime factorizations of some integer strictly smaller than {{math|n}}, which contradicts the minimality of {{math|n}}.Uniqueness without Euclid's lemma
The fundamental theorem of arithmetic can also be proved without using Euclid's lemma.{{citation |last1=Dawson |first1=John W. |title=Why Prove it Again? Alternative Proofs in Mathematical Practice. |date=2015 |publisher=Springer |isbn=9783319173689 |page=45}} The proof that follows is inspired by Euclid's original version of the Euclidean algorithm. Assume that s is the smallest positive integer which is the product of prime numbers in two different ways. Incidentally, this implies that s, if it exists, must be a composite number greater than 1. Now, say
begin{align}s&=p_1 p_2 cdots p_m &=q_1 q_2 cdots q_n.end{align}Every p_i must be distinct from every q_j. Otherwise, if say p_i=q_j, then there would exist some positive integer t=s/p_i=s/q_j that is smaller than {{mvar|s}} and has two distinct prime factorizations. One may also suppose that p_1 < q_1, by exchanging the two factorizations, if needed.Setting P=p_2cdots p_m and Q=q_2cdots q_n, one has s=p_1P=q_1Q.Also, since p_1 < q_1, one has Q < P.It then follows that
s-p_1Q = (q_1-p_1)Q = p_1(P-Q) < s.
As the positive integers less than {{mvar|s}} have been supposed to have a unique prime factorization, p_1 must occur in the factorization of either q_1-p_1 or {{mvar|Q}}. The latter case is impossible, as {{mvar|Q}}, being smaller than {{mvar|s}}, must have a unique prime factorization, and p_1 differs from every q_j. The former case is also impossible, as, if p_1 is a divisor of q_1-p_1, it must be also a divisor of q_1, which is impossible as p_1 and q_1 are distinct primes.Therefore, there cannot exist a smallest integer with more than a single distinct prime factorization. Every positive integer must either be a prime number itself, which would factor uniquely, or a composite that also factors uniquely into primes, or in the case of the integer 1, not factor into any prime.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 of Gaussian integers, the set of all complex numbers a + bi where a and b are integers. It is now denoted by mathbb{Z}[i]. He showed that this ring has the four units ±1 and ±i, that the non-zero, non-unit numbers fall into two classes, primes and composites, and that (except for order), the composites have unique factorization as a product of primes (up to the order and multiplication by units).Gauss, BQ, §§ 31â34Similarly, in 1844 while working on cubic reciprocity, Eisenstein introduced the ring mathbb{Z}[omega], where omega = frac{-1 + sqrt{-3}}{2}, omega^3 = 1 is a cube root of unity. This is the ring of Eisenstein integers, and he proved it has the six units pm 1, pmomega, pmomega^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{{Harvtxt|Hardy|Wright|2008|loc=§ 14.6}}
6 =
2 cdot 3 =
left(1 + sqrt{-5}right)left(1 - sqrt{-5}right).
Examples like this caused the notion of "prime" to be modified. In mathbb{Z}left[sqrt{-5}right] it can be proven that if any of the factors above can be represented as a product, for example, 2 = ab, then one 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; for example, 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 in mathbb{Z}left[sqrt{-5}right] (only divisible by itself or a unit) but not prime in mathbb{Z}left[sqrt{-5}right] (if it divides a product it must divide one of the factors). The mention of mathbb{Z}left[sqrt{-5}right] is required because 2 is prime and irreducible in mathbb{Z}. Using these definitions it can be proven that in any integral domain a prime must be irreducible. Euclid's classical lemma can be rephrased as "in the ring of integers mathbb{Z} every irreducible is prime". This is also true in mathbb{Z}[i] and mathbb{Z}[omega], but not in mathbb{Z}[sqrt{-5}].The rings in which factorization into irreducibles is essentially unique are called unique factorization domains. Important examples are polynomial rings over the integers or over a field, Euclidean domains and principal ideal domains.In 1843 Kummer introduced the concept of ideal number, which was developed further by Dedekind (1876) into the modern theory of ideals, special subsets of rings. Multiplication is defined for ideals, and the rings in which they have unique factorization are called Dedekind domains.There is a version of 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
- {{annotated link|Integer factorization}}
- {{annotated link|Prime signature}}
Notes
{{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.
| last = Gauss | first = Carl Friedrich
| translator-last = Clarke | translator-first = Arthur A.
| title = Disquisitiones Arithemeticae (Second, corrected edition)
| publisher =
Springer | location = New York
| year = 1986
| isbn = 978-0-387-96254-2
| url =
weblink
}}
| last = Gauss | first = Carl Friedrich
| translator-last = Maser | translator-first = H.
| language = de
| 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".
| last1 = Gauss | first1 = Carl Friedrich
| title = Theoria residuorum biquadraticorum, Commentatio prima
| publisher = Comment. Soc. regiae sci, Göttingen 6
| location = Göttingen
| year = 1828}}
| 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.
| 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 =
weblink | url-access = registration
| ref = {{harvid|Euclid|Heath|1956}}
}}
- {{Hardy and Wright|mode=cs2}}
- {{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
}}.
| 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
}}.
| 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{edih}
- {{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 }}
External links
{{Divisor classes}}
- content above as imported from Wikipedia
- "fundamental theorem of arithmetic" does not exist on GetWiki (yet)
- time: 6:02pm EDT - Wed, May 01 2024
[ this remote article is provided by Wikipedia ]
© 2024 M.R.M. PARROTT | ALL RIGHTS RESERVED