8.5: Applications in Number Theory

Induction (or the fact that \(\mathbb{N}\) is well-ordered) can be used to prove many important properties of natural numbers. Here are just three examples.

Definition \(8.5.1\).

An element \(p\) of \(\mathbb{N}^{+}\) is prime iff \(p > 1\) and \(p\) is not divisible by any element of \(\mathbb{N}^{+}\) other than 1 and \(p\).

Proposition \(8.5.2\).

If \(n \in \mathbb{N}\) and \(n > 1\), then \(n\) is divisible by a prime number.

Proof

Suppose there is some natural number \(n > 1\), such that \(n\) is not divisible by a prime number. (This will lead to a contradiction.) Since \(\mathbb{N}\) is well-ordered, we may assume that \(n\) is the smallest such number, so: \[\text { If } 1<k<n \text { (and } k \in \mathbb{N} \text { ), then } k \text { is divisible by a prime number. }\]

Since \(n \mid n\), but (by assumption) \(n\) is not divisible by any prime number, we know that \(n\) is not prime. By definition, this means there exists \(k \in \mathbb{N}\), such that \(k \mid n\) and \(1 < k < n\). From the minimality of \(n\), we know that \(k\) is divisible by some prime number \(p\). Then \(p \mid k\) and \(k \mid n\), so \(p \mid n\). This contradicts the fact that \(n\) is not divisible by a prime number.

Theorem \(8.5.3\) (Fundamental Theorem of Arithmetic).

Every natural number (other than 0 and 1) is a product of prime numbers (or is itself a prime).

Proof

BY CONTRADITION: Suppose there is some natural number \(n > 1\), such that \(n\) is not a product of prime numbers (and is not a prime). Since \(\mathbb{N}\) is well-ordered, we may assume that \(n\) is the smallest such number, so: \[\text { If } 1<k<n \text { (and } k \in \mathbb{N}), \text { then } k \text { is a product of prime numbers. }\]

Since \(n\) is not prime, it is divisible by some natural number \(k\), with \(1 < k < n\). This means we may write \(n = km\), for some \(m \in \mathbb{N}^{+}\). Since \(m = n / k\) and \(1 < k < n\), we see that \(1 < m < n\). Therefore, the minimality of \(n\) implies that \(k\) and \(m\) are products of prime numbers: say \(k=p_{1} p_{2} \cdots p_{r}\) and \(m=q_{1} q_{2} \cdots q_{s}\). Then \[n=k m=\left(p_{1} p_{2} \cdots p_{r}\right)\left(q_{1} q_{2} \cdots q_{s}\right)\]

is a product of prime numbers. This is a contradiction.

Remark \(8.5.4\).

In fact, every natural number can be written in only one way as a product of prime numbers (up to rearranging the order of the factors), but we will not prove this fact.

Definition \(8.5.5\).

Let \(a, b \in \mathbb{N}^{+}\). We say \(a\) and \(b\) are relatively prime iff they have no divisors in common, other than 1. (I.e., if \(k \in \mathbb{N}^{+}\), and \(k\) is a divisor of both \(a\) and \(b\), then \(k = 1\). In other words, the “greatest common divisor” of \(a\) and \(b\) is 1.)

Theorem \(8.5.6\).

Let \(a, b \in \mathbb{N}^{+}\). If \(a\) and \(b\) are relatively prime, then there exist \(m, n \in \mathbb{Z}\), such that \(ma + nb = 1\).

Proof

Let \[S=\{m a+n b \mid m, n \in \mathbb{Z} k=\} \cap \mathbb{N}^{+} .\]

It is easy to see that \(a \in S\) (by letting \(m = 1\) and \(n = 0\)), so \(S \neq \varnothing\). Therefore, since \(\mathbb{N}\) is well-ordered, we may let \(d\) be the smallest element of \(S\). Then \(d \in S\), so we have \(d = m_{0}a+n_{0}b\) for some \(m_{0}, n_{0} \in \mathbb{Z}\).

By the Division Algorithm \((5.1.20)\), we may write \[a=q d+r \text { with } 0 \leq r<d .\]

So \[r=a-q d=a-q\left(m_{0} a+n_{0} b\right)=\left(1-q m_{0}\right) a+q n_{0} b=m a+n b ,\]

where \(m = 1 − qm \in \mathbb{Z}\) and \(n = qn \in \mathbb{Z}\). On the other hand, since \(r < d\), and \(d\) is the smallest element of \(S\), we know \(r \notin S\). From the definition of \(S\), we conclude that \(r = 0\). So \(d \mid a\).

By repeating the same argument with \(a\) and \(b\) interchanged (and \(m_{0}\) and \(n_{0}\) also interchanged) we see that \(d \mid b\).

Therefore, \(d\) is a divisor of both \(a\) and \(b\). Since \(a\) and \(b\) are relatively prime, we conclude that \(d = 1\). Since \(d \in S\), this means \(1 \in S\), which establishes the desired conclusion.

Exercise \(8.5.7\).

Prove the converse of Theorem \(8.5.6\).

Theorem \(8.5.6\) is of fundamental importance in Number Theory, the mathematical study of properties of \(\mathbb{N}\) and \(\mathbb{Z}\). Here are a few of its many consequences:

Exercise \(8.5.8\).

Assume \(a, b \in \mathbb{N}^{+}\).

1. Show \(a\) and \(b\) are relatively prime iff there exists \(x \in \mathbb{Z}\), such that \(x a \equiv 1(\bmod b)\).
2. Show \(a\) and \(b\) are relatively prime iff for all \(y \in \mathbb{Z}\), there exists \(x \in \mathbb{Z}\), such that \(x a \equiv y(\bmod b)\).
3. (Chinese Remainder Theorem) Suppose \(a\) and \(b\) are relatively prime. For all \(y_{1}, y_{2} \in \mathbb{Z}\), show there exists \(x \in \mathbb{Z}\), such that \(x \equiv y_{1}(\bmod a)\) and \(x \equiv y_{2}(\bmod b)\).

Proposition \(8.5.2\) also has important consequences. For example:

Corollary \(8.5.9\).

There are infinitely many prime numbers.

Proof

BY CONTRADICTION: Suppose there are only finitely many prime numbers. Then we can make a list of all of them: \[\text { The set of all prime numbers is }\left\{p_{1}, p_{2}, \ldots, p_{n}\right\} .\]

Let \[N=p_{1} p_{2} \cdots p_{n} .\]

From Proposition \(8.5.2\), we know there is some prime \(p\), such that \(p \mid (N + 1)\).

Since \(p_{1}, p_{2}, \ldots, p_{n}\) is a list of all the prime numbers, we know \(p = p_{i}\), for some \(i\). Therefore \(p = p_{i}\) is one of the factors in the product that defines \(N\), so \(p \mid N\). Therefore, \(p\) divides both \(N\) and \(N + 1\), so (from \(5.1.9(1)\)) we have \[p \mid((N+1)-N)=1 .\]

This implies \(p = \pm 1\) (see page 97), which contradicts the fact that \(p\), being a prime number, must be \(> 1\).