Lecture 5: Prime numbers

\( \newcommand{\set}[1]{\{#1\}} \newcommand{\comprehension}[2]{\{#1\,\vert\,#2\}} \newcommand{\size}[1]{\vert#1\vert} \newcommand{\true}{\top} \newcommand{\false}{\bot} \newcommand{\limplies}{\rightarrow} \newcommand{\divides}{\mathbin{\vert}} \newcommand{\mult}{\mathbin{\cdot}} \newcommand{\xor}{\oplus} \newcommand{\union}{\cup} \newcommand{\intersect}{\cap} \newcommand{\complement}[1]{\overline#1} \newcommand{\powerset}{\mathcal{P}} \newcommand{\ixUnion}{\bigcup} \newcommand{\ixIntersect}{\bigcap} \newcommand{\Div}{\mathrm{div}} \newcommand{\gcd}{\mathrm{gcd}} \newcommand{\divmod}{\mathop{\mathbf{divmod}}} \newcommand{\div}{\mathop{\mathbf{div}}} \newcommand{\mod}{\mathop{\mathbf{mod}}} \)

Administrivia

Prime Numbers

Last time, we looked at modular arithmetic, and in doing so encountered prime numbers in a variety of ways. Today, we're going to look more intentionally at the primes themselves, and particularly (for the sake of simplicity), primes in $\mathbb{N}$.

Theorem 5.1 Every natural number $n>1$ has a prime divisor.

The standard way to prove universal statements in number theory is by induction. But while inductive ideas are central to the proof of Theorem 5.1, a straightforward inductive argument doesn't work. Let's examine the issue: What I want to prove amounts to this: $\forall n,\, n > 1 \limplies \exists p, \text{prime}(p) \land p \divides n$.

If I approach this in the obvious way, in my inductive step, I'll have the inductive hypothesis that $n > 1 \limplies \exists p, \text{prime}(p) \land p \divides n$, and the obligation to prove that $n+1 > 1 \limplies \exists p, \text{prime}(p) \land p \divides n+1$. So, I'll assume $n+1 > 1$ and argue that $n+1$ is either prime or it's not. If it's prime, I'm good: $n+1$ is prime, and $n+1 \divides n+1$, witnessing the inner existential. If $n+1$ is not prime, then I can represent it as a non-trivial product $n+1 = a \mult b$, where $a$, $b$ are neither zero nor units, so $1 \lt a, b \lt n+1$. So what I want to do is appeal to my inductive hypothesis to get a prime factor $p$ of $a$, and then use the transitivity of divisibility to conclude that $p \divides n+1$.

But I can't: there's a mismatch between what I need (i.e., that non-trivial $a \leq n$ have prime factors), and what I have (that if $n$ is non-trivial, it has a prime factor). My inductive hypothesis is too weak! This is a recurring problem, and the solution is to search for a stronger statement, which will enable me to use a stronger inductive hypothesis. But this particular obstruction comes up often enough that it's worth building a special purpose framework.

Definition 5.2 (The Principle of Strong Induction) $(\forall n,\, (\forall k \lt n, \varphi(k)) \limplies \varphi(n)) \limplies \forall n,\, \varphi(n)$.

The intuition behind the principle of proof by strong induction is essentially the same as the intuition behind the usual principle of proof by induction. A statement $\forall n,\, \varphi(n)$ is either true or false. If we assume for a contradiction that it is false, then the set $\comprehension{n}{\lnot \varphi(n)}$ is a non-empty set of natural numbers, and so it contains a least-counter example $n_0$. As $n_0$ is a least counter-example, we must have $\forall k \lt n_0,\, \varphi(k)$. If we can prove $\forall n, (\forall k \lt n, \varphi(k)) \limplies \varphi(n_0)$, then we must have $\varphi(n_0)$, contradicting the choice of $n_0$ as a counter-example.

As a theoretical matter, the principles of induction and strong induction are equivalent: we can prove each from the other. In practice, strong induction has a lot going for it: we have fewer hypotheses to show (one vs. two), and the hypothesis we get is stronger (we get to assume that our proposition of interest is true for all smaller values, and not just for our predecessor). This is exactly the additional power we need to prove Theorem 5.1.

Proof of Theorem 5.1. By strong induction on the statement $\varphi(n) = n > 1 \limplies \exists p,\, \text{prime}(p) \land p \divides n$.

Assume $\varphi(k)$ is true whenever $k \lt n$. Assume $n > 1$. If $n$ is prime, then $n \divides n$, and we're done. So assume $n$ is not prime. Then $n$ can be written as a non-trivial product $n = a \mult b$, where $1 \lt a,b \lt n$. By our inductive hypothesis, at $a$, $\exists p,\, \text{prime}(p) \land p \divides a$. As divisibility is transitive, $p \divides n$, establishing $\varphi(n)$. The result follows.

$\Box$ Theorem 5.1

Theorem 5.3 There exist infinitely many primes.

Proof Assume for a contradiction that $p_1,p_2,\ldots,p_k$ is a complete list of all the prime natural numbers. Consider $n = p_1\mult p_2 \mult \ldots \mult p_k + 1$. Clearly, $n$ is relatively prime to all of the $p_i$'s. By Theorem 5.1, let $p$ be a prime dividing $n$. Clearly, $p$ must also be relatively prime to all of the $p_i$'s, and therefore can't equal any of them, contradicting the claim that $p_1,p_2,\ldots,p_k$ is a complete list of all the primes.

$\Box$ Theorem 5.3

Theorem 5.4 (The Fundamental Theorem Arithmetic) Every $n>1$ can be written uniquely (up to order) as a product of primes.

Proof

*Exercise 5.5 Prove the existential part of this theorem by strong induction on $n$.

For uniqueness, let's first prove the following:

Lemma 5.6 If $p$ is prime, $p_1, \ldots, p_k$ are prime (not necessarily distinct), and $p \divides p_1 \mult \ldots \mult p_k$, then $p = p_i$ for some $i$.

Proof of Lemma 5.6. By induction on $k$. The $k=0$ case is vacuous, so we'll start with $k=1$.

Basis case: $k=1$. Our hypothesis is that $p \divides p_1$. This can only occur in $\mathbb{N}$ if $p = p_1$, as required.

Induction case. Suppose the lemma is true for $k$, and consider an instance of the $k+1$ case, i.e., $p \divides p_1 \mult \ldots p_k \mult p_{k+1}$. Recall Corollary 4.17: if $p \divides a \mult b$, then $p \divides a$ or $p \divides b$. Take $a = p_1 \mult \ldots p_k$ and $b = \mult p_{k+1}$. If $p \divides a$, then $p = p_i$ for some $i \in \set{1,\ldots,k}$ by our inductive hypothesis. If $p \divides b$, then $p \divides p_{k+1}$, and so $p=p_{k+1}$.

$\Box$ Lemma 5.6

Returning to the proof of the uniqueness (up to order) of a prime factorization. Suppose prime factorizations aren't unique. Let $n$ be the least natural number that doesn't have a unique prime factorization. Thus $n = p_1 \mult \ldots \mult p_k = p_1' \mult \ldots \mult p_{k'}'$, where the $p_i$'s and $p_i'$'s differ by more than order. Now, $p_1 \divides n$, and so by the lemma, we must have $p_1 = p_j'$ for some $j$. We can then divide both sides of the equality by $p_1$, obtaining a smaller counter-example, contradicting the minimality of $n$.

$\Box$ Theorem 5.4

Note that our proof of uniqueness, which involved reasoning directly about a least counter-example, is really a proof by strong induction.

Definition 5.7 We define the factorial function $n!$ by induction on $n$ as

\begin{align*} 0! &= 1\\ (n+1)! &= n! \mult (n+1) \end{align*}

Informally, $n! = 1 \mult 2 \mult \ldots \mult n$ is the product of the first $n$ non-zero natural numbers. The factorial function is important in counting arguments (and for this reason, we're going to get very familiar with it), but also in number theory. The following theorem (and proof!) are remarkable:

Theorem 5.8 (Wilson's Theorem) For all $p$ prime, $(p-1)! = -1 \pmod{p}$.

Proof Consider the equation $x^2 = 1 \pmod{p}$. We can rewrite this as $x^2-1=0 \pmod{p}$, and then factor the left-hand side resulting in $(x-1)\mult(x+1) = 0 \pmod{p}$. Using the fact that for primes $p$, if $p \divides a \mult b$, then either $p \divides a$ or $p\divides b$, we infer $x-1 = 0 \pmod{p}$ or $x+1 = 0 \pmod{p}$, i.e., $x = \pm 1 \pmod{p}$.

A consequence of this is that if $x \in \set{2,3,\ldots,p-2}$, then $x^{-1} \not= x \pmod{p}$. As a result, we can reorder the middle terms of the factorial $(p-1)!$ into distinct pairs of numbers and their multiplicative inverses. Those pairs multiply to $1$ each, and disappear in the product, leaving us with $1 \mult -1 = -1 \pmod{p}$.

$\Box$ Theorem 5.8

Example 5.9 Consider Wilson's Theorem when $p = 11$:

\begin{align*} 10! &= 1 \mult 2 \mult 3 \mult 4 \mult 5 \mult 6 \mult 7 \mult 8 \mult 9 \mult 10 &\pmod{11}\\ &= 1 \mult (2 \mult 6) \mult (3 \mult 4) \mult (5 \mult 9) \mult (7 \mult 8) \mult 10 &\pmod{11}\\ &= 1 \mult (1 \mult 1 \mult 1 \mult 1) \mult -1 &\pmod{11}\\ &= -1 &\pmod{11} \end{align*}

Lemma 5.10 Let $p$ be prime, and $a$ be such that $\gcd(a,p) = 1$. Then $\set{a \mult 1, a \mult 2, \ldots, a \mult (p-1)} = \set{1,2,\ldots,p-1}$.

This is easy to see: as $\gcd(a,p) = 1$, we know that there's a multiplicative inverse $a^{-1}$ for $a$. We can recover the set $\set{1,2,\ldots,p-1}$ from $\set{a \mult 1, a \mult 2, \ldots, a \mult (p-1)}$ by multiplying through by $a^{-1}$, so there is a one-one correspondence between the two sets.

Theorem 5.11 (Fermat's Little Theorem) For all primes $p$, and $a$ such that $\gcd(a,p)=1$, $a^{p-1} = 1 \pmod{p}$.

Proof Consider the product $n = (a \mult 1) \mult (a \mult 2) \mult \ldots \mult (a \mult (p-1)) \pmod{p}$. On one hand, by the lemma, this is just a reordering of the factorial, and so $n = -1$ by Wilson's Theorem. On the other hand, we can factor the $a$'s out, so $n = a^{p-1} \mult (p-1)! \pmod{p}$. Applying Wilson's Theorem again, we see $n = a^{p-1} \mult (-1) \pmod{p}$. Equating, and multiplying through by $-1$, yields the desired result.

$\Box$ Theorem 5.11

Example 5.12 Compute $3^{100,000} \mod 7$.

We certainly don't want to compute $3^{100,000}$ by hand, divide by $7$, and return the remainder. But we can divide $100,000$ by $6 = 7-1$, resulting in $100,000 = 16,666 \mult 6 + 4$, and therefore

\begin{align*} 3^{100,000} &= 3^{16,666 \mult 6 + 4} &\pmod{7}\\ &= (3^6)^{16,666} \mult 3^4 &\pmod{7}\\ &= 1^{16,666} \mult 9^2 &\pmod{7}\\ &= 2^2 &\pmod{7}\\ &= 4 &\pmod{7} \end{align*}

Exercise 5.13 Compute $3^{1000} \mod 13$.

Example 5.14 Let's try something more complicated. Compute $5^{1000} \mod 77$.

We can't apply Fermat's Little Theorem directly, as $77 = 7 \mult 11$ is not prime. But we can use it to compute $5^{1000} \mod 7$ and $5^{1000} \mod 11$, and then combine our answers using the Chinese Remainder Theorem. Thus,

\begin{align*} 5^{1000} &= 5^{166\mult 6 + 4} &\pmod{7}\\ &= 5^4 &\pmod{7}\\ &= 25^2 &\pmod{7}\\ &= 4^2 &\pmod{7}\\ &= 16 &\pmod{7}\\ &= 2 &\pmod{7} \end{align*}

and

\begin{align*} 5^{1000} &= 5^{100\mult 10 + 0} &\pmod{11}\\ &= 5^0 &\pmod{11}\\ &= 1&\pmod{11} \end{align*}

Now, we just need to solve the equations

\begin{align*} 5^{1000} &= 2 &\pmod{7}\\ 5^{1000} &= 1 &\pmod{11} \end{align*}

To this end, we compute $7^{-1} = 8 \pmod{11}$ and $11^{-1} = 4^{-1} = 2 \pmod {7}$, and obtain the solution

\begin{align*} 5^{1000} &= 2 \mult 2 \mult 11 + 1 \mult 8 \mult 7 &\pmod{77} \\ &= 44 + 56 &\pmod{77}\\ &= 100 &\pmod{77}\\ &= 23 &\pmod{77} \end{align*}

*Exercise 5.15 Compute $5^{10,000} \mod 52$.

Primes function as the building blocks of the natural numbers, from a multiplicative point of view. We've seen that there are infinitely many primes, but this does not give us much information about how often they occur among the natural numbers. The following, classical, theorem gives us much more insight:

Theorem 5.16 (Prime Density Theorem) Let $\pi(n)$ be the number of primes less than or equal to $n$. Then $\pi(n) \sim {n\over \ln(n)}$, where $\ln$ is the natural logarithm function.

The original proof of this theorem used analysis, i.e., continuous methods. There now exist so-called “elementary” proofs that are formulated in Peano Arithmetic, but they are not simple, and indeed, are well beyond this course.