Skip to main content

Section 8.4 The Fundamental Theorem of Arithmetic (FTA)

The fundamental theorem of arithmetic says that all integers have a unique factorization as a product of powers of prime numbers.

We will split the proof into three lemmas:

Remark: If \(n\) is prime, this statement still makes sense: we just interpret \(n\) as being the product of just one number, \(n\) itself.

We prove by strong induction on \(n\text{.}\) The case \(n=2\) immediately holds (taking into account the previous remark). For the induction step, suppose the theorem holds for all integers \(n\lt N\text{.}\) If \(N\) is prime, there is nothing to prove; otherwise, if \(N\) is not prime, then \(N=a\cdot b\) for some positive integers \(a\) and \(b\text{,}\) both greater than \(1\) and less than \(N\text{.}\) Both \(a\) and \(b\) can be decomposed by the strong induction hypothesis, thus so can \(n=ab\text{.}\)

By the previous lemma, \(n=q_{1}\cdots q_\ell\) for some primes \(q_{1}\cdots q_{\ell}\) that are not necessarily distinct. If \(p_{1}\lt p_{2}\lt \cdots \lt p_{k}\) are the distinct primes that appear in the list \(q_{1},...,q_{\ell}\text{,}\) let \(r_{i}\) denote the number of times that \(p_{i}\) appears in the list. Then

\begin{equation*} n=q_{1}\cdots q_{\ell} = p_{1}^{r_{1}}\cdots p_{k}^{r_{k}} \end{equation*}

which proves the lemma.

Suppose \(p_1^{r_{1}}\cdots p_k^{r_{k}} = n = q_1^{s_{1}}\cdots q_\ell^{s_{\ell}}\) are two decompositions. By cancelling any common factors, we can assume that no \(p_i\) equals any \(q_j\text{.}\) If there are any \(p_i's\) and \(q_j's\) remaining, Corollary 8.3.5 implies each \(p_{i}\) equals some \(q_j\text{,}\) which is a contradiction, thus there can be no terms remaining, so the two factorizations must have been equal.

Let's use the FTA to solve another simple-looking diophantine equation.

Find all integer solutions to \(x^{2}=y^{5}\text{.}\)

Solution.

We want to apply the FTA to \(x\) and \(y\text{,}\) but this only works when \(x,y\geq 2\text{.}\) Note that if \((x,y)\) is a solution, then so is \((-x,y)\text{,}\) so we just need to find all solutions with \(x\geq 0\text{.}\) The only solutions with \(x=0\) is \((0,0)\) and the only solution with \(x=1\) or \(y=1\) is \((1,1)\text{.}\) Thus, we have narrowed things down to just finding all solutions \((x,y)\) with \(x,y\geq 2\text{.}\)

By the FTA, there are primes \(p_{1}\lt \cdots \lt p_{k}\) and \(q_{1}\lt \cdots \lt q_{\ell}\) and \(r_{i},s_{j}\in \NN\) so that

\begin{equation*} x=p_{1}^{r_{1}}\cdots p_{k}^{r_{k}}\;\;\; \mbox{ and } \;\;\; y= q_1^{s_{1}}\cdots q_\ell^{s_{\ell}}\text{.} \end{equation*}

Plugging this into \(x^2=y^5\text{,}\) we get

\begin{equation*} p_{1}^{2r_{1}}\cdots p_{k}^{2r_{k}} = q_1^{5s_{1}}\cdots q_\ell^{5s_{\ell}}\text{.} \end{equation*}

The FTA says these two factorizations must equal, so \(k=\ell\text{,}\) \(p_i=q_i\text{,}\) and \(2r_{i}=5s_{i}\) for \(1\leq i\leq k\text{.}\) By Example 8.3.6, this means \(r_{i}=5w_{i}\) and \(s_{i}=2w_{i}\) for some integer \(w_{i}\text{.}\) Thus,

\begin{equation*} x=p_{1}^{5w_{1}}\cdots p_{k}^{5w_{k}}= \left(p_{1}^{w_{1}}\cdots p_{k}^{w_{k}}\right)^{5} \;\;\; \mbox{ and } \;\;\; y =p_1^{2w_{1}}\cdots p_\ell^{2w_{\ell}} = \left(p_1^{w_{1}}\cdots p_\ell^{w_{\ell}}\right)^2\text{.} \end{equation*}

If we let \(z=p_1^{w_{1}}\cdots p_\ell^{w_{\ell}}\text{,}\) we see that \((x,y)=(z^{5},z^{2})\text{.}\) Thus, we have shown that all integer solutions \(x,y\geq 2\) are of the form \((x,y)=(z^{5},z^{2})\) for some \(z\in\NN\text{.}\) Recalling our reductions, all solutions are either \((0,0)\text{,}\) \((\pm 1,1)\text{,}\) and \((\pm z^5,z^2)\) for \(z\in\NN\text{.}\) More succinctly, all solutions must be of the form \(( z^5,z^2)\) for some \(z\in\ZZ\text{.}\) One can also easily check that every pair in this set is also a solution to \(x^2=y^5\text{,}\) thus \(S\) is exactly the set of solutions.

Note 8.4.6. Reductions.

Look for ways of simplifying your problem from the start by reducing the number of cases you have to investigate. The next problem is a good example of how to find reductions.

Find all integer solutions to \(x^2-y^2=91\text{.}\)

Reductions: Let's make a few observations first to narrow down what to solve for.

  • Notice that if \((x,y)\) is a solution, then so is \((\pm x,\pm y)\text{,}\) and so we can assume that \(x,y\geq 0\text{,}\) since then the other solutions will be of the form \((\pm x,\pm y)\text{.}\)

  • Moreover, we can't have \(x=y\) since then the equation is not satisfied, so assume \(x\neq y\text{.}\) We can also assume \(x>y\text{,}\) since \(x\lt y\) would imply \(x^2\lt y^2\text{,}\) so \(x^2-y^2\lt 0\lt 51\text{.}\)

  • Finally, we can't have either \(x\) or \(y\) equal to zero, since \(91\) is not a perfect square.

Thus, after these reductions, we can assume \(x>y>0\text{.}\)

Note that \(91\) has prime factorization \(91=7\cdot 13\text{,}\) and so

\begin{equation*} 91=7\cdot 13 = x^2-y^2=(x-y)(x+y)\text{.} \end{equation*}

Since \(x+y>x-y\text{,}\) there are two cases to consider:

  • If \(x+y=91\) and \(x-y=1\text{,}\) solving these linear equations simultaneously gives \(x=46\) and \(y=45\text{.}\)

  • If \(x+y=13\) and \(x-y=7\text{,}\) solving these two equations gives \(x=10\) and \(y=3\text{.}\)

Thus, all the positive solutions \((x,y)\) are \((46,45)\) and \((10,3)\text{.}\) Thus, recalling our reductions, all solutions are just \((\pm 46, \pm 45)\text{,}\) and \((\pm 10,\pm 3)\) (where we range over all possible combinations of \(\pm\) for a total of \(8\) solutions).