2.4: Corollaries of the Fundamental Theorem of Arithmetic

The unique factorization theorem is intuitive and easy to use. It is very effective in proving a great number of results. Some of these results can be proved with a little more effort without using the theorem (see exercise 2.5 for an example).

Corollary 2.15

For all \(a\) and \(b\) in \(\mathbb{Z}\) not both equal to \(0\), we have that \(\gcd(a, b) \cdot \mbox{lcm} (a, b) = ab\) up to units.

Proof

If \(c\) is a divisor or multiple of \(a\), then so is \(-c\). So \(a\) and \(-a\) have the same divisors and multiples. Therefore without loss of generality we may assume that \(a\) and \(b\) are positive.

Given two positive numbers \(a\) and \(b\), let \(P = \{p_{i}\}^{k}_{i=1}\) be the list of all prime numbers occurring in the unique factorization of \(a\) or \(b\). We then have:

\[\begin{array}{ccc} {a = \prod_{i=1}^{s} p_{i}^{k_{i}}}&{and}&{b = \prod_{i=1}^{s} p_{i}^{l_{i}}} \end{array} \nonumber\]

where \(k_{i}\) and \(l_{i}\) in \(\mathbb{N} \cup \{0\}\). Now define:

\[\begin{array} {ccc} {m_{i} = \mbox{ min} (k_{i},l_{i})}&{and}&{M_{i} = \mbox{ max} (k_{i},l_{i})} \end{array} \nonumber\]

and let the numbers \(m\) and \(M\) be given by

\[\begin{array}{ccc} {m = \prod_{i=1}^{s} p_{i}^{m_{i}}}&{and}&{M = \prod_{i=1}^{s} p_{i}^{M_{i}}} \end{array} \nonumber\]

Since \(m_{i} + M_{i} = k_{i} + l_{i}\), it is clear that the multiplication \(m \cdot M\) yields \(ab\).

Now all we need to do, is showing that \(m\) equals \(\gcd (a,b)\) and that \(M\) equals \(\mbox{lcm}(a,b)\). Clearly \(m\) divides both \(a\) and \(b\). On the other hand, any integer greater than \(m\) has a unique factorization that either contains a prime not in the list \(P\) and therefore divides neither \(a\) nor \(b\), or, if not, at least one of the primes in \(P\) in its factorization has a power greater than \(m_{i}\). In the last case \(m\) is not a divisor of at least one of \(a\) and \(b\). The proof that \(M\) equals \(\mbox{lcm} (a,b)\) is similar.

A final question one might ask, is how many primes are there? In other words, how long can the list of primes in a factorization be? Euclid provided the answer around 300BC.

Theorem 2.16 (Infinity of Primes)

There are infinitely many primes.

Proof

Suppose the list \(P\) of all primes is finite, so that \(P = \{p_{i}\}^{n}_{i=1}\). Define the integer \(d\) as the product of all primes (to the power \(1\)):

\[d = \prod_{i=1}^{n} p_{i} \nonumber\]

If \(d+1\) is a prime, we have a contradiction. So \(d+1\) must be divisible by a prime \(p_{i}\) in \(P\). But then we have

\[\begin{array} {ccc} {p_{i}|d}&{and}&{p_{i}+1|d} \end{array} \nonumber\]

But since \((d+1)(1)+d(-1) = 1\), Bezout's lemma implies that \(\gcd (d,d+1) = 1\), which contradicts our earlier conclusion \(p_{i} | d\)

One the best known consequences of the fundamental theorem of arithmetic is probably the theorem that follow below. A special case, namely \(\sqrt{2}\) is irrational (see theorem 1.11), was known to Pythagoras in the 6th century BC.

Theorem 2.17

Let \(n > 0\) and \(k > 1\) be integers. Then \(n^{\frac{1}{k}}\) is either an integer or irrational.

Proof

Assume \(n^{\frac{1}{k}}\) is rational. That is: suppose that there are integers \(a\) and \(b\) such that

\[n^{\frac{1}{k}} = \frac{a}{b} \Rightarrow n \cdot b^k = a^k \nonumber\]

Divide out any common divisors of \(a\) and \(b\), so that \(\gcd (a,b) = 1\). Then by the fundamental theorem od arithmetic:

\[n \prod_{i=1}^{s} p_{i}^{km_{i}} = \prod_{i=s+1}^{r} p_{i}^{kl_{i}} \nonumber\]

Therefore, in the factorization of \(n\), each prime \(p_{i}\) must occur with a power that is a non-negative multiple of \(k\). Because \(\gcd (a,b) = 1\), the prime \(p_{i}\) on the left and right side are distinct. This is only possible if \(\prod_{i=1}^{s} p_{i}^{km_{i}}\) equals \(1\). But then \(n\) is the k-th power of an integer.

Lemma 2.18

We have

\[\forall i \in \{1,\cdots, n\} : \gcd (a_{i},b) = 1 \Leftrightarrow \gcd (\prod_{i=1}^{n} a_{i},b) = 1 \nonumber\]

Proof

The easiest way to see this uses prime power fractorization. If \(\gcd (\prod_{i=1}^{n} a_{i},b) = d > 1\), then \(d\) contains a factor \(p > 1\) that is a prime. Since \(p\) divides \(\prod_{i=1}^{n} a_{i}\), at least one of the \(a_{i}\) must contain (by Corollary 2.11) a factor \(p\). Since \(p\) also divides \(b\), this contradicts the assumption that \(\gcd (a_{i},b) = 1\).

Vice versa, if \(\gcd(a_{i} , b) = d > 1\) for some \(i\), then also \(\prod_{i=1}^{n} a_{i}\) is divisible by \(d\).