Number Theory Home

## Prime Factorization

Theorem.(Fundamental Theorem of Arithmetic) Every integer greater than $$1$$ can be written as a product of primes and the product is unique if prime factors are written in non-decreasing order.

Example. $$1176=2\cdot 2\cdot 2\cdot 3\cdot 7 \cdot 7=2^3\cdot 3^1\cdot 7^2.$$

In the unique prime factorization we can replace the product of the same prime by a prime power to get a unique prime-power factorization: Every integer $$n>1$$ can be written as $n=p_1^{a_1}\cdot p_2^{a_2}\cdots p_k^{a_k},$ for some unique primes $$p_1< p_2<\cdots < p_k$$ and unique positive integers $$a_1,a_2,\ldots,a_k.$$

Note that if $$1$$ were prime, then we do not have the uniqueness in the prime factorization. For example, $$3=1\cdot 3=1\cdot 1\cdot 3.$$

Proof of FTA. (Existence) We prove the existence of prime factorization of $$n>1$$ by induction. For $$n=2$$, $$n$$ is a prime which is a prime product with a single term. Suppose we have prime factorization for all integers $$n=2,3,\ldots,k$$. Let $$n=k+1$$. If $$n=k+1$$ is a prime, then it is a prime product with a single term. Otherwise $$n=k+1=ab$$ for some integers $$a,b,\; 1< a,b < k+1$$. By the induction hypothesis, $$a=p_1\cdot p_2\cdots p_r$$ and $$a=q_1\cdot q_2\cdots q_s$$ for some primes $$p_1,p_2,\ldots, p_r, q_1,q_2,\ldots, q_s$$. Then $$n=k+1=ab=p_1\cdot p_2\cdots p_r\cdot q_1\cdot q_2\cdots q_s$$. So by mathematical induction we have prime factorization for all integers $$n>1$$. ◼

To prove the uniqueness of prime factorization, we need the following results.

Lemma.(Euclid's Lemma) Let $$a$$ and $$b$$ be integers. If a prime $$p\vert ab$$, then $$p\vert a$$ or $$p\vert b$$.

Proof. If $$p\vert a$$, we are done. Otherwise $$p\nmid a$$ and consequently $$\gcd(a,p)=1$$. By Bézout's Lemma, $$1=\gcd(a,p)=ax+py$$ for some integers $$x$$ and $$y$$. Then $$b=abx+pby$$. Since $$p\vert ab$$ and $$p\vert pb$$, $$p\vert abx+pby=b$$. ◼

Applying Euclid's lemma inductively we get the following result.

Corollary. Let $$p$$ be a prime and $$a_1,a_2,\ldots,a_n$$ be integers.

1. If $$p\vert a_1\cdot a_2\cdots a_n$$, then $$p\vert a_k$$ for some $$k=1,2,\ldots,n$$.

2. If $$p\vert a_1\cdot a_2\cdots a_n$$ and $$a_1,a_2,\ldots,a_n$$ are primes, then $$p=a_k$$ for some $$k=1,2,\ldots,n$$.

Proof of FTA. (Uniqueness) Suppose $$n=p_1\cdot p_2\cdots p_r$$ and $$n=q_1\cdot q_2\cdots q_s$$ for some primes $$p_1\leq p_2 \leq\cdots\leq p_r$$, $$q_1\leq q_2\leq\cdots\leq q_s$$. We show $$r=s$$ and $$p_i=q_i$$ for $$i=1,2,\ldots,r$$. Since $$p_1\vert q_1\cdot q_2\cdots q_s$$, $$p_1=q_k$$ for some $$k$$ by the preceding corollary. Then $$p_1\geq q_1$$. Similarly we can show that $$q_1\geq p_1$$. Thus $$p_1=q_1$$ and $$p_2\cdot p_3\cdots p_r=q_2\cdot q_3\cdots q_s$$. Repeating this process, we get $$p_2=q_2$$ and $$p_3\cdot p_4\cdots p_r=q_3\cdot q_4\cdots q_s$$. Continuing this process we get $$p_r=q_r$$ and $$1=q_{r+1}\cdots q_s$$ if $$rs$$. Since each $$p_i,q_j>1$$, we cannot have $$1=q_{r+1}\cdots q_s$$ and $$p_{s+1}\cdots p_r=1$$. Thus $$r=s$$ and $$p_i=q_i$$ for $$i=1,2,\ldots,r$$. ◼

Last edited