Fundamental Theorem of Arithmetic

Direct Knowlege Contributor David A. Smith
  • By David A. Smith, Founder & CEO, Direct Knowledge
  • David Smith has a B.S. and M.S. in Mathematics and has enjoyed teaching calculus, linear algebra, and number theory at both Tarrant County College and the University of Texas at Arlington. David is the Founder and current CEO of Direct Knowledge.

First we characterize prime numbers in terms of divisibility. We then use this characterization to prove the Fundamental Theorem of Arithmetic –that every positive integer has a unique factorization into a product of primes. We also discuss greatest common divisors and least common multiples.

Finally, we will also provide the proof to the theorem, which should help clarify why 1 is not considered a prime number. Hopefully, this proof will also help shed more light on the existence, as well as the uniqueness, of these prime factors.

Introduction to the Fundamental Theorem of Arithmetic

The Fundamental Theorem of Arithmetic states that every natural number greater than 1 is either a prime or a product of a finite number of primes and this factorization is unique except for the rearrangement of the factors. Before we prove the fundamental fact, it is important to realize that not all sets of numbers have this property.

Where unique factorization fails

For example, let us consider the set of even integers, namely $$ E= \{ 2k \mid k\in \mathbb{Z} \}. $$ We can add, subtract, even multiply elements of $E,$ and obtain elements in $E,$ so we say the set $E$ is closed under addition, subtraction, and multiplication. However, this is not the set of integers so we should define what we mean by divisibility; namely for any two elements of E we say $a | b$ means there exists $m\in E$ such that $b=m a.$ The importance of $m\in E$ should not be overlooked. For example, $2|8$ because $8=m (2)$ where $m=4\in E.$ But $2\nmid 6$ because there is no $m\in E$ such that $6=m (2)$.

So what are some primes in $E$? For example, 2 is prime in $E$ because there does not exist $n, m$ in $E$ such that $2=n m$. Similarly, 6 is prime in $E$ because there does not exist $n, m$ in $E$ such that $6=n m$. Also, 10 and 30 are primes, and so $60=2(30)$ is not. However since $60=10(6)$ we conclude that factorization into primes in $E$ is not unique.

Characterization of Prime Numbers

Before getting to the Fundamental Theorem of Arithmetic (a survey) we need an important result.

Lemma. (Prime Characterization) A natural number $p$ is a prime if and only if $$ p | b c \implies (p | b \text{ or } p | c) $$ for any natural numbers $b$ and $c.$

Proof. Assume $p$ is prime and $p|b c$. Notice that, since $p$ is prime, either $(p,b)=1$ or $(p,b)=p.$ If $(p,b)=1,$ it follows that $p|c.$ If $(p,b)=p$ then $p|b$. In either case, $p|c$ or $p|b.$ Conversely, suppose $$ \forall \, b, c \in \mathbb{N}, \, p|b c\implies \text{$p|c$ or $p|b$}. $$ To show that $p$ is prime let $d$ be a divisor of $p.$ Then $p=d t$ for some $t$. Hence we have $p | d$ or $p | t.$ Thus, if $t=p k$ for some $k,$ then $p=d t=d p k,$ and so $d=\pm 1.$ If $d=p k$ for some $k,$ then $p=p t k$ and so $d=\pm p$. Therefore, the only divisors of $p$ are $d=\pm 1, \pm p$, and so $p$ is prime.

Example. Prove if $p$ is a prime number, $a_1, a_2, \ldots, a_n$ are natural numbers, and $p\left|a_1a_2\cdots a_n\right. ,$ then $p\left|a_i\right.$ for some $1\leq i\leq n.$

Solution. The statement is clearly true when $n=1$ and $n=2.$ Assume the statement is true for $n=k,$ and suppose $p\left|a_1a_2\cdots a_ka_{k+1}.\right.$ Hence, $p\left|a_1a_2\cdots a_k\right.$ or $p\left|a_{k+1}.\right.$ If $p\left|a_{k+1}\right.$, the statement is proven. If not, then by the induction hypothesis there is some $0\leq i\leq k$ such that $p | a_i$. Therefore, there is some $0\leq i\leq k+1$ such that $p | a_i$ as desired.

Trial Division

The most basic method of checking the primality of a given integer $n$ is called trial division. This method consists of dividing $n$ by each integer $m$ that is greater than 1 and less than or equal to the square root of $n$. If the result of any of these divisions is an integer, then $n$ is not a prime, otherwise it is a prime. For example, for $n = 37,$ the trial divisions are by $m = 2, 3, 4, 5, $ and 6. None of these numbers divides $37,$ so $37$ is prime.

Lemma. Every natural number greater than 1 is a product of primes.

Proof. Consider the set $S$ consisting of all positive natural numbers greater than 1 that are not a product of primes. Assume for a contradiction that $S$ is not empty, then by the Well-Ordering Axiom there is a least element, say $m$. Because $m$ has no prime divisors and $m$ divides $m$, we see that $m$ is not prime. Thus, $m=a b$ where $1<a<m$ and $1<b<m$. Since $m$ is the least element in $S$, $a$ and $b$ are products of primes; and thus so is $m$. This contradiction shows that $S$ is empty and so every natural number greater than $1$ is a product of primes.

Proof of the Fundamental Theorem of Arithmetic

The Fundamental Theorem of Arithmetic, also called the unique factorization theorem or the unique-prime-factorization theorem, states that every integer greater than 1 is either is prime itself or is the product of prime numbers, and that, although the order of the primes in the second case is arbitrary, the primes themselves are not.

Theorem. (Fundamental Theorem of Arithmetic) Every natural number greater than 1 can be written uniquely in the form $$ n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k} $$ where $p_1 < p_2 < \cdots < p_k$ are prime numbers and $e_1, e_2, \ldots , e_k$ are natural numbers.

Proof. Every natural number has a prime factorization as shown above. Thus existence is proven. Now we prove uniqueness. If there is an natural number greater than 1 for which the factorization is not unique, then by the Well-Ordering Axiom there exists a smallest such natural number, say $m.$

Assume that $m$ has two prime factorizations say $$ m=p_1^{\alpha _1}p_2^{\alpha _2}\cdots p_s^{\alpha _s} $$ and $$m=q_1^{\beta_1}q_2^{\beta_2}\cdots q_t^{\beta_t}, $$ where $$ p_1 < p_2 < \cdots < p_s \qquad q_1 < q_2 < \cdots < q_t $$ and the $\alpha _i$ and $\beta _j$ are all positive for $0\leq i\leq s$ and $0\leq j\leq  t.$  Therefore we have $$ q_1\mid p_{i^*} \text{ for some } 1\leq  i^*\leq  s \quad \text{ and } \quad p_1\mid q_{j^*} \text{ for some } 1\leq j^*\leq t. $$ Since all the numbers $p_i$ and $q_j$ are prime, we must have $q_1=p_{i^*}$ and $p_1=q_{j^*}.$ Then $i^*=j^*=1$ since $$ q_1\leq q_{j^*}=p_1\leq p_{i^*}=q_1. $$ Let $u$ be the natural number defined as $$ u=\frac{m}{p_1}=\frac{m}{q_1}=p_1^{\alpha _1-1}p_2^{\alpha _2}\cdots  p_s{}^{\alpha _s}=q_1^{\beta _1-1}q_2^{\beta_2}\cdots  q_t{}^{\beta _t}.$$ If $u=1,$ then $m=p_1$ has a unique factorization contrary to hypothesis. If $u>1,$ then $u<m$ and $u$ has two factorizations. Both cases reveal that $m$ can not exist as desired.

An Application of the Fundamental Theorem of Arithmetic

The Fundamental Theorem of Arithmetic is an integral pillar in Number Theory, specifically due to its extensive application in various contexts. The basic idea of the theorem is that any integer greater than one is either prime, or can be expressed as a product of prime factors.

As such, we can exploit this concept to make work easier when we want to find the greatest common divisor of a number, or even the least common multiple of a number. The Theorem allows us to express the given number as a product of its prime factors, hence making it easy to establish the greatest common divisor or the least common multiple.

Example. Show there are infinitely many primes of the form $4n+3.$

Solution. First notice that the product of any two natural numbers of the form $4n+1$ also has the form $4n+1$ which can be seen by letting $a=4s+1$ and $b=4r+1$ where $s$ and $r$ are natural numbers, then $$ a b=(4s+1)(4r+1)=16 r s+4 r+4 s+1=4(4 r s+r+s)+1. $$ We assume there are only a finite number of primes of the form $4k+3,$ say $p_0=3,p_1,\ldots ,p_n$ is all of them; and we consider the natural number $$Q=4p_1p_2\cdots p_n+3. $$

Notice that the prime factorization of $Q$, namely $Q=q_1\cdots q_t\cdots q_m$ must contain at least one prime of the form $4k+3$ because otherwise $Q$ would be of the form $4k+1.$ Thus, there is one prime in the prime factorization of $Q$ that is of the form $4k+3$ say $q_t.$ Either $q_t=3$ or $q_t>3.$ If $q_t=3,$ then $3|Q$ which means $3|(Q-3)$ and so $3\left|4p_1\cdots p_n\right.$ which is absurd. If $q_t>3,$ then $q_t=p_j$ for some $1\leq j\leq n$ and so $\left.q_t\right|Q$ implies $q_t|Q-4p_1\cdots p_n=3,$ which is also absurd. Therefore, there are infinitely many primes of the form $4n+3.$

Least Common Multiples

The concept of least common multiple of a given set of numbers is premised on the idea that the factors of these numbers aggregate to a unique, smallest value for which all are divisors. It therefore leverages the power of the Fundamental Arithmetic Theorem to establish such a unique smallest number.

Definition. The least common multiple of two nonzero natural numbers $a$ and $b$ is the smallest positive natural number that is divisible by $a$ and $b.$

The least common multiple of $15$ and 21 is $[15,21]=105.$ The least common multiple of $24$ and 36 is $[24,36]=72.$ The least common multiple of 2 and 20 is $[2,20]=20.$ The least common multiple of 7 and 11 is $[7,11]=77.$

Unique Prime Factorization

Corollary. Let $a$ and $b$ be natural numbers. Then \begin{equation*} (a,b)=p_1^{\min \left(\alpha _1,\beta_1\right)} p_2^{\min \left(\alpha _2, \beta_2\right)} \cdots p_n^{\min \left(\alpha_1,\beta_1\right)} = p_1^{\max \left(\alpha _1,\beta_1\right)} p_2^{\max \left(\alpha _2,\beta_2\right)} \cdots p_n^{\max \left(\alpha_1,\beta_1\right)}. \end{equation*}

Proof. By the Fundamental Theorem of Arithmetic, one is able to find the greatest common divisor and least common multiple from a factorization of two given natural numbers. Say we are given $a$ and $b,$ and we are able to find the unique factorization of each (and assume that all exponents are non-negative and the $p_i$ are all primes in both $a$ and $b$), namely $$ a=p_1^{\alpha _1} p_2^{\alpha _2} \cdots p_n^{\alpha _n} \qquad \text{ and } \qquad b=p_1^{\beta_1}p_2^{\beta_2}\cdots p_m^{\beta_m} $$ then because for each prime $p_i,$ in $a$ and $b$ have exactly $\min \left(\alpha _i,\beta_i\right)$ factors of $p_i$ in common; and

Example. Find the unique prime factorization of $m=4463914455$ and $n=8125921375.$ Then factor $m$ and $n$ into a product of primes with the same set of primes with (possibly zero) nonnegative exponents.

Solution. Notice $4463914455=3^4\cdot 5\cdot 7^2\cdot 11^3\cdot 13^2$ and $8125921375=5^3\cdot 11^3\cdot 13^2\cdot 17^2.$ Thus the set of primes in both natural numbers is ${3,5,7,11,13,17}$ and so we have
\begin{align} & 4463914455=3^4\cdot 5\cdot 7^2\cdot 11^3\cdot 13^2 \cdot 17^0 \\ & 8125921375=3^0\cdot 5^3\cdot 7^0\cdot 11^3\cdot 13^2\cdot 17^2. \end{align}

Greatest Common Divisors and Least Common Multiples

Finding the greatest common divisor of a number, or the least common multiple of a given set of numbers is a simple mathematical process that relies on the factorization concept covered by the Fundamental Theorem of Arithmetic. An interesting relationship, however, exists between the GCD and the LCM.

Corollary. (Product of GCD and LCM) If $a$ and $b$ are integers, then $(a,b) [a,b]=a b.$

Proof. Let $a$ and $b$ have unique prime factorizations (by the Fundamental Theorem of Arithmetic); namely $$ a=p_1^{u_1}p_2^{u_2} \cdots p_n^{u_n} $$ and $$ b=q_1^{v_1}q_2^{v_2} \cdots q_m^{v_m}. $$ Now we can form the set of primes $P_1, \ldots ,P_k$ consists of all the $p_1,p_2, \ldots ,p_n$ and $q_1,q_2 , \ldots ,q_m.$ So we can write $$ a=P_1^{\alpha _1}P_2^{\alpha _2}\cdots P_n^{\alpha _n} $$ and $$ b=P_1^{\beta_1}P_2^{\beta_2}\cdots P_m^{\beta_m} $$ where the exponents are zero where necessary. Now let $X_i=\max \left(\alpha _i,\beta_i\right)$ and $x_i=\min \left(\alpha _i,\beta_i\right).$ Then \begin{align*} ab & =P_1^{X_1}P_1^{X_1}\cdots P_n^{X_n}P_1^{x_1}P_1^{x_1}\cdots P_n^{x_n} \\ & =P_1 ^{X_1+x_1}P_1 ^{X_1+x_1}\cdots P_n^{X_1+x_1} \\ & =a b. \end{align*} as desired.

Examples on GCD and LCM

Example. Prove that, if $a, b,$ and $c$ are natural numbers, then $ [a,b] | c $ if and only if $a|c$ and $b|c.$

Solution. Suppose $[a,b]|c.$ Since $a|[a,b]$ and $b|[a,b]$ it follows that $a|c$ and $b|c.$ Conversely, suppose $a|c$ and $b|c.$ Using prime factorization we can write $$ a=p_1^{a_1}\cdot p_2^{a_2}\cdots p_n^{a_n}, \qquad b=p_1{}^{b_1}\cdot p_2^{b_2}\cdots p_n^{b_n},\qquad c=p_1^{c_1}\cdot p_2^{c_2}\cdots p_n^{c_n}. $$ Then $\max \left(a_i,b_i\right)\leq c_i$ for $i=1,2, \ldots ,n$ because $a|c$ and $b|c.$ Hence, $[a,b]\mid c$.

Let $p$ be a prime and $n$ a positive integer. If $\left.p^a\right|n$ but $p^{a+1}\nmid n,$ we say that $p^a$ exactly divides $n$ and we write $\left.p^a\right|n.$

Example. Prove that, if $a$ and $b$ are positive natural numbers, then $(a,b)=(a+b,[a,b]).$

Solution. Let $p$ be a prime that divides $a$ or $b.$ Then $p$ divides $a+b$ and $[a,b].$ Hence $p$ divides both sides. Define, $s$ and $t$ by $\left.p^s\right|a$ and $\left.p^t\right|b,$ say $a=x p^s$ and $b=y p^t.$ Without loss of generality, suppose $s\leq t.$ Then $$a+b=p^s\left(x+p^{t-s}\right), $$ so $\left.p^s\right|(a+b).$ Also, $\left.p^{\max (s,t)}\right|[a,b].$ But $\max (s,t)=t,$ so $\left.p^t\right|[a,b].$ Therefore, $$ \left.p^{\min (s,t)}\right|(a+b,[a,b]). $$ But $\min (s,t)=s,$ so the same power of $p$ divides both sides. Therefore, the two sides must be equal.

Exercises on the Fundamental Theorem of Arithmetic

Exercise. Find the unique prime factorization of $12446784$ and of $2293834752.$

Exercise. Factor $12446784$ and $2293834752$ into a product of primes with the same set of primes with (possibly zero) nonnegative exponents.

Exercise. Find a prime factorization of a) 111,111, b) 100000, c) 10,500,000, and d) $10!.$

Exercise. Show that all of the prime powers in the prime-power factorization of an integer $n$ are even if and only if $n$ is a perfect square.

Exercise. Show that if $a$ and $b$ are positive integers and $a^3|b^2,$ then $a|b.$

Exercise. Find the greatest common divisor of each of the following pairs of integers:

$(1) \quad 2^13^25^3$, $2^23^37^2 $

$(2) \quad 2(3)(5)(7), 7(11)(13) $

$(3) \quad 2^83^65^411^{13}$, $2(3)(5)(11)(13) $

$(4) \quad 41^{101}47^{43}103^{1001}$, $41^{11}43^{47}83^{111}$

Exercise. Find the least common multiple of each of the following pairs of integers:

$(1) \quad 2^23^35^57^7$, $2^73^55^37^2$

$(2) \quad 2(3)(5)(7)(11)$, $17(19)(23)(29)$

$(3) \quad 2^35^711^{13}$, $2(3)(5)(7)(11)(13)$

$(4) \quad 47^{11}79^{111}101^{1001}$, $41^{11}83^{111}101^{1000}$

Exercise. Find the least common multiple of each of the following pairs of integers:

$(1) \quad 2^23^35^57^7$, $2^73^55^37^2$

$(2) \quad 2(3)(5)(7)(11)$, $17(19)(23)(29)$

$(3) \quad 2^35^711^{13}$, $2(3)(5)(7)(11)(13)$

$(4) \quad 47^{11}79^{111}101^{1001}$, $41^{11}83^{111}101^{1000}$

Exercise. If $p$ is a prime and $a$ is an integer with $p\left|a^2\right.$ then $p|a.$ Hint: use the Fundamental Theorem of Arithmetic.

Exercise. Show that if $a,$ $b,$ and $c$ are integers with $c|a b$ then $c|(a,c)(b,c).$

Exercise. Find the prime factorization of

$(1) \quad 33,776,925$

$(2) \quad 210,733,237$

$(3) \quad 1,359,170,111$

$(4) \quad 33,108,075$

$(5) \quad 7,300,977,607$

$(6) \quad 4,165,073,376,607$.

Exercise. Show that any number of the form $2^{4 n+2}+1$ can be factored easily and then show how to factor $2^{18}+1.$

Additional Exercises on the Fundamental Theorem of Arithmetic

Exercise. Find the unique prime factorization of $12446784$ and of $2293834752.$ Factor $12446784$ and $2293834752$ into a product of primes with the same set of primes with (possibly zero) nonnegative exponents.

Exercise. Find a prime factorization of $111111$, $100,000$, $10,500,000$, and $10!$.

Exercise. Show that all of the prime powers in the prime-power factorization of an integer $n$ are even if and only if $n$ is a perfect square.

Exercise. Show that if $a$ and $b$ are positive integers and $a^3|b^2,$ then $a|b.$

Exercise. Show that if $a,$ $b,$ and $c$ are integers with $c|a b$ then $c|(a,c)(b,c).$

Exercise. Show that if $p$ is prime, $a$ is an integer, and $n$ is a positive integer such that $p\left|a^n\right.,$ then $p|a.$

Exercise. Show that if $\left.p^a\right|m$ and $\left.p^b\right|n,$ then $\left.p^{a+b}\right| n m.$

Exercise. Show that if $\left.p^a\right|m$ then $p^{k a}|m^k$ for any positive integer $k.$

Exercise. Show that if $\left.p^a\right|m$ and $\left.p^b\right|n$ with $a\neq b,$ then $\left.p^{\min (a,b)}\right|(m+n).$

Exercise. Use the unique factorizations of $n=5248$ and $m=1280$ to determine the unique factorizations of $(n,m)$and $[n,m].$

Exercise. Show that if $a$ and $b$ are positive integers, then $(a,b)=(a+b,[a,b]).$

Exercise. Write out the unique prime factorization of $1494411775.$ Show each step.

Leave a Comment