Difference between revisions of "Fundamental Theorem of Arithmetic"
(→Proofs) |
|||
(One intermediate revision by the same user not shown) | |||
Line 3: | Line 3: | ||
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: <math>30 = 2 \cdot 15 = 3 \cdot 10 = 5 \cdot 6</math>. Thus, the Fundamental Theorem of Arithmetic tells us in some sense that "factorizations into prime numbers is deeper than factorization into two parts." | 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: <math>30 = 2 \cdot 15 = 3 \cdot 10 = 5 \cdot 6</math>. Thus, the Fundamental Theorem of Arithmetic tells us in some sense that "factorizations into prime numbers is deeper than factorization into two parts." | ||
− | == | + | == Proof == |
The most common elementary proof of the theorem involves induction and use of [[Euclid's Lemma]], which states that if <math>a</math> and <math>b</math> are natural numbers and <math>p</math> is a prime number such that <math>p \mid ab</math>, then <math>p \mid a</math> or <math>p \mid b</math>. This proof is not terribly interesting, but it does prove that every [[Euclidean domain]] has unique prime factorization. | The most common elementary proof of the theorem involves induction and use of [[Euclid's Lemma]], which states that if <math>a</math> and <math>b</math> are natural numbers and <math>p</math> is a prime number such that <math>p \mid ab</math>, then <math>p \mid a</math> or <math>p \mid b</math>. This proof is not terribly interesting, but it does prove that every [[Euclidean domain]] has unique prime factorization. | ||
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> | ||
− | |||
− | |||
{{stub}} | {{stub}} | ||
[[Category:Number theory]] | [[Category:Number theory]] |
Latest revision as of 23:28, 4 August 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."
Proof
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
are Jordan-Hölder series, and their quotients are
and
Then by the Jordan-Hölder Theorem, the primes
are a rearrangement of the primes
. Therefore the prime factorization of
is unique.
This article is a stub. Help us out by expanding it.