Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Fundamental Theorem of Arithmetic"

m
(added some)
Line 1: Line 1:
−
The '''Fundamental Theorem of Arithmetic''' states that every [[positive integer]] <math>n</math> can be written as a product <math>n = p_1 \cdot p_2 \cdot \cdots \cdot p_k</math> where the <math>\displaystyle p_i</math> are all [[prime number]]s; moreover, this [[expression]] for <math>n</math> (called its [[prime factorization]]) is unique, up to rearrangement of the factors.
+
The '''Fundamental Theorem of Arithmetic''' states that every [[positive integer]] <math>n</math> can be written as a product <math>n = p_1 \cdot p_2 \cdot \cdots \cdot p_k</math> where the <math>p_i</math> are all [[prime number]]s; moreover, this [[expression]] for <math>n</math> (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: <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."
 +
 +
== Proofs ==
 +
 +
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 proof below uses [[group theory]], specifically the [[Jordan-Hölder Theorem]].
 +
 +
=== Proof by Group Theory ===
 +
 +
Suppose that <math>n = p_1 \dotsm p_n = q_1 \dotsm q_m</math>, for primes <math>p_i</math> and <math>q_i</math>.  Then both of the [[composition series]]
 +
<cmath> \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}, </cmath>
 +
<cmath> \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} </cmath>
 +
are [[Jordan-Hölder series]], and their [[quotient group | quotient]]s are
 +
<cmath> \mathbb{Z}/p_1\mathbb{Z}, \mathbb{Z}/p_2\mathbb{Z}, \dotsc, \mathbb{Z}/p_n \mathbb{Z} </cmath>
 +
and
 +
<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>
  
 
{{stub}}
 
{{stub}}
 +
 +
[[Category:Number theory]]

Revision as of 21:42, 13 May 2008

The Fundamental Theorem of Arithmetic states that every positive integer $n$ can be written as a product $n = p_1 \cdot p_2 \cdot \cdots \cdot p_k$ where the $p_i$ are all prime numbers; moreover, this expression for $n$ (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: $30 = 2 \cdot 15 = 3 \cdot 10 = 5 \cdot 6$. 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 $a$ and $b$ are natural numbers and $p$ is a prime number such that $p \mid ab$, then $p \mid a$ or $p \mid b$. 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 $n = p_1 \dotsm p_n = q_1 \dotsm q_m$, for primes $p_i$ and $q_i$. 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},\] \[\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}\] 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}\] and \[\mathbb{Z}/q_1\mathbb{Z}, \mathbb{Z}/q_2\mathbb{Z}, \dotsc, \mathbb{Z}/q_m \mathbb{Z} .\] Then by the Jordan-Hölder Theorem, the primes $q_1, \dotsc, q_m$ are a rearrangement of the primes $p_1, \dotsc, p_n$. Therefore the prime factorization of $n$ is unique. $\blacksquare$

This article is a stub. Help us out by expanding it.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Fundamental_Theorem_of_Arithmetic&oldid=25992"