Difference between revisions of "Fundamental Theorem of Arithmetic"
(added some) |
|||
| Line 19: | Line 19: | ||
<cmath> \mathbb{Z}/q_1\mathbb{Z}, \mathbb{Z}/q_2\mathbb{Z}, \dotsc, \mathbb{Z}/q_m \mathbb{Z} .</cmath> | <cmath> \mathbb{Z}/q_1\mathbb{Z}, \mathbb{Z}/q_2\mathbb{Z}, \dotsc, \mathbb{Z}/q_m \mathbb{Z} .</cmath> | ||
Then by the [[Jordan-Hölder Theorem]], the primes <math>q_1, \dotsc, q_m</math> are a rearrangement of the primes <math>p_1, \dotsc, p_n</math>. Therefore the prime factorization of <math>n</math> is unique. <math>\blacksquare</math> | Then by the [[Jordan-Hölder Theorem]], the primes <math>q_1, \dotsc, q_m</math> are a rearrangement of the primes <math>p_1, \dotsc, p_n</math>. Therefore the prime factorization of <math>n</math> is unique. <math>\blacksquare</math> | ||
| + | ===Proof by Ring Theory=== | ||
| + | Since <math>\mathbb{Z}</math> is a Euclidean Domain, it is a Principle Ideal Domain, and is therefore a Unique Factorization Domain. This proves the theorem <math>\blacksquare</math> | ||
{{stub}} | {{stub}} | ||
[[Category:Number theory]] | [[Category:Number theory]] | ||
Revision as of 10:32, 3 March 2022
The Fundamental Theorem of Arithmetic states that every positive integer 
can be written as a product 
where the 
are all prime numbers; moreover, this expression for (called its prime factorization) is unique, up to rearrangement of the factors.
Note that the property of uniqueness is not, in general, true for other sorts of factorizations. For example, most integers have many factorizations into 2 parts: 
. Thus, the Fundamental Theorem of Arithmetic tells us in some sense that "factorizations into prime numbers is deeper than factorization into two parts."
Proofs
The most common elementary proof of the theorem involves induction and use of Euclid's Lemma, which states that if 
and 
are natural numbers and 
is a prime number such that 
, then 
or 
. This proof is not terribly interesting, but it does prove that every Euclidean domain has unique prime factorization.
The proof below uses group theory, specifically the Jordan-Hölder Theorem.
Proof by Group Theory
Suppose that 
, for primes and 
. Then both of the composition series
![\[\mathbb{Z}/n\mathbb{Z}, \mathbb{Z}/(n/p_1)\mathbb{Z}, \mathbb{Z}/(n/p_1 p_2) \mathbb{Z}, \dotsc, \mathbb{Z}/\mathbb{Z},\]](http://latex.artofproblemsolving.com/b/1/e/b1e65ba247a2ce32e62c5cdc24cbea162843e08d.png)
![\[\mathbb{Z}/n\mathbb{Z}, \mathbb{Z}/(n/q_1)\mathbb{Z}, \mathbb{Z}/(n/q_1 q_2) \mathbb{Z}, \dotsc, \mathbb{Z}/\mathbb{Z}\]](http://latex.artofproblemsolving.com/6/5/7/657620d78826a73d8375b0261d9afb5b581f8455.png)
are Jordan-Hölder series, and their quotients are
![\[\mathbb{Z}/p_1\mathbb{Z}, \mathbb{Z}/p_2\mathbb{Z}, \dotsc, \mathbb{Z}/p_n \mathbb{Z}\]](http://latex.artofproblemsolving.com/a/b/c/abc7d74dc292f814282647ae121526f540f491c7.png)
and
![\[\mathbb{Z}/q_1\mathbb{Z}, \mathbb{Z}/q_2\mathbb{Z}, \dotsc, \mathbb{Z}/q_m \mathbb{Z} .\]](http://latex.artofproblemsolving.com/d/e/6/de6556baff34725506e7a5c59e3a948e16922785.png)
Then by the Jordan-Hölder Theorem, the primes 
are a rearrangement of the primes 
. Therefore the prime factorization of is unique. 
Proof by Ring Theory
Since 
is a Euclidean Domain, it is a Principle Ideal Domain, and is therefore a Unique Factorization Domain. This proves the theorem
This article is a stub. Help us out by expanding it.
