Fermat and Induction

Section 5.5 Fermat and Induction

In this section we will prove some of the conjectures from investigations. To do this we will introduce the idea of proof by induction. Before reading this section make sure you have completed Investigation: Discrete Logs, Investigation: Power Patterns, and Investigation: More Mod Patterns.

One of the conjectures from the investigations involved nice patterns with combinations mod \(p\text{.}\)

Theorem 5.5.1. Prime Combinations Theorem.

For a prime number \(p\text{,}\) \(C(p,0)=1\text{,}\) \(C(p,p)=1\text{,}\) and for \(0 \lt k \lt p \text{,}\) \(C(p,k) \equiv 0 \mod p\text{.}\)

Before proving this, let's look at an example.

Example 5.5.2.

\(C(11,3)=\frac{11!}{8!3!}=\frac{11\times 10\times 9}{6}=11\times 5 \times 3\text{.}\) Note, the important part is that the 6 in the denominator has factors in common with 10 and 9, but has no factors in common with 11. So \(C(11,3)\) is a multiple of 11.

Let's compare this to \(C(12,3)=\frac{12!}{9!3!}=\frac{12\times 11\times 10}{6}=4 \times 11 \times 5\text{.}\) In this case, In this case the 6 in the denominator does have factors in common with 12 and some of these factors (namely the 3) cannot be cancelled out with any of the other terms, so that C(12,3) is not a multiple of 12.

Thus \(C(11,3) \equiv 0 \mod 11\) but \(C(12,3) \not\equiv 0 \mod 12\text{.}\)

We should now be ready for the proof!

Proof.

Recall that \(C(p,k)=\frac{p!}{k!(p-k)!}\text{.}\)

For the first formula, \(C(p,0)=\frac{p!}{0!(p-0)!}=1\text{.}\)

For the second formula, \(C(p,p)=\frac{p!}{p!(p-p)!}=1\text{.}\)

For the third formula, let \(0 \lt k \lt p\text{,}\)

\begin{equation*} C(p,k)=\frac{p!}{k!(p-k)!}=\frac{p\times(p-1)!}{k!(p-k)!}\text{.} \end{equation*}

We know \(C(p,k)\) is an integer since it is the number of way to choose \(k\) objects from a set of \(p\) objects. So \(k!(p-k)!\) must divide \(p!\text{.}\) We claim \(k!(p-k)!\) must actually divide \((p-1)!\text{.}\) To see that, we note that \(p\) is prime. Thus, the only divisors of \(p\) are 1 and \(p-1\text{.}\) Since \(0 \lt k \lt p\) then \(-p \lt -k \lt 0\) and by adding \(p\) to all sides we have \(0 \lt p-k \lt p\text{.}\) Therefore, there will be no factor of \(p\) in either \(k!\) or \((p-k)!\text{.}\) Thus all factors of \(k!\) and \((p-k)!\) must divide \((p-1)!\) and

\begin{equation*} C(p,k)=\frac{p!}{k!(p-k)!}=\frac{p\times(p-1)!}{k!(p-k)!}=p\times\frac{(p-1)!}{k!(p-k)!}. \end{equation*}

Since \(\frac{(p-1)!}{k!(p-k)!}\) must be an integer, we have \(C(p,k) \equiv 0 \pmod{p}\text{.}\)

For the next result about \((x+y)^p \mod p\text{,}\) we need to recall the binomial theorem.

Theorem 5.5.3. Binomial Theorem.

The expansion for \((x+y)^n\) for a positive integer \(n\) is given by

\begin{equation*} (x+y)^n = \sum_{i=0} ^n C(n,i)x^{n-i}y^{i}. \end{equation*}

To illustrate the idea of the proof for The Wishful Thinking Theorem, we look at an example.

Example 5.5.4.

\begin{equation*} (x+y)^5=C(5,0)x^5+C(5,1)x^4y+C(5,2)x^3y^2+C(5,3)x^2y^3+C(5,4)xy^4+C(5,5)y^5. \end{equation*}

Now we can use the previous theorem to evaluate all of the coefficients mod 5 and see that \((x+y)^5 \equiv x^5 + y^5 \pmod{5}\text{.}\)

Theorem 5.5.5. Wishful Thinking Theorem.

For a prime number \(p\text{,}\) \((x+y)^p \equiv x^p + y^p \mod p\text{.}\)

Proof.

Let \(p\) be a prime. By the Binomial Theorem we have \((x+y)^p=C(p,0)x^p + C(p,1)x^{p-1}y + C(p,2)x^{p-2}y^2+ \cdots C(p,p-1)x^1y^{p-1}+C(p,p)y^p\text{.}\) By above theorem we have \(C(p,0)=1\text{,}\) \(C(p,p)=1\text{,}\) and for \(0 \lt k \lt p \text{,}\) \(C(p,k) \equiv 0 \mod p\text{.}\) Thus, \((x+y)^p \equiv x^p + 0 + 0+ \cdots 0+y^p \pmod{p}\text{.}\)

We are almost ready to prove our first conjecture and explain our number trick for primes. In order to do that, we will need to do proof by induction.

Principle 5.5.6. Principle of Mathematical Induction.

A proof by induction for a statement involving positive integers \(n\) consists of two parts:

A base case. Let \(n=1\) or whatever the smallest value of \(n\) that is true for the statement. Show the statement is true for that specific value of \(n\text{.}\)

An inductive step. Show that an if-then statement is true. Show that if the statement is true for \(n=k\) for some value of \(k\) then the statement is true for the next value of \(k\text{,}\) namely \(k+1\text{.}\) It's important to note in this step that you are proving an if-then statement about how the statement for \(k\) implies the statement for \(k+1\text{.}\) You are not proving either of the statements about \(k\) or \(k+1\text{.}\)

The idea of proof by induction is that for a mathematical statement \(S(n)\) we show:

Base Case. \(S(1)\) is true.
Inductive step once. We show if \(S(1)\) is true then \(S(2)\) is true. Since we showed \(S(1)\) is true, this now implies \(S(2)\) is true.
Inductive step twice. We show if \(S(2)\) is true then \(S(3)\) is true. Since we showed \(S(2)\) is true, this now implies \(S(3)\) is true.
Inductive step third time. We show if \(S(3)\) is true then \(S(4)\) is true. Since we showed \(S(3)\) is true, this now implies \(S(4)\) is true.
We can keep applying the inductive step recursively to show that By the recursive nature of the inductive step, we can keep doing this until \(S(n)\) is true for all positive integers \(n \geq 1\text{.}\) We do this generically by showing that if \(S(k)\) is true then \(S(k+1)\) is true for any \(k\text{.}\)

We will start with a simpler example of an induction proof and then use it to prove our big theorem!

Theorem 5.5.7.

For all positive integers, \(n \geq 1\text{,}\) \(1+2+3 \cdots +(n-1)+n = \frac{n(n+1)}{2}\text{.}\)

Proof.

For our base case, we have \(n=1\text{.}\) We examine the left hand side (LHS) and the right hand side (RHS) separately.

LHS: 1

RHS: \(\frac{1(1+1)}{2}=\frac{1(2)}{2}=1\text{.}\)

Since the left hand side and the right hand side are equal for \(n=1\text{,}\) the base case is established.

For the inductive step, we assume the statement is true for some \(k\text{.}\) (Note: not all \(k\text{,}\) just one, say \(k=1\)) for our if-then statement. We need to show if \(1+2+3+ \cdots +k=\frac{k(k+1)}{2}\) then \(1+2+3+ \cdots +k+1=\frac{(k+1)\times((k+1)+1)}{2}=\frac{(k+1)(k+2)}{2}\text{.}\) We start by assuming \(1+2+3+ \cdots +k=\frac{k(k+1)}{2}\) and examine how to convert this equation into the desired statement for \(k+1\text{.}\) The easiest thing to do is add \(k+1\) to both sides:

\begin{align*} 1+2+3+ \cdots +k\amp=\frac{k(k+1)}{2}\\ 1+2+3+ \cdots +k + (k+1)\amp=\frac{k(k+1)}{2}+(k+1)\\ \amp = \frac{k(k+1)+2(k+1)}{2}\\ \amp = \frac{(k+1)(k+2)}{2}. \end{align*}

Thus by induction, we have \(1+2+3 \cdots +(n-1)+n = \frac{n(n+1)}{2}\) for all \(n \geq 1\text{.}\)

We are now ready to prove the main theorem that will explain our number trick for prime numbers.

Theorem 5.5.8. Fermat's Little Theorem.

Let \(p\) by a prime then \(x^p \equiv x \pmod{p}\text{.}\) Moreover, if \(\gcd(p,x)=1\) then \(x^{p-1} \equiv 1 \pmod{p}\text{.}\)

Proof.

We will prove this by induction on \(x\) and The Wishful Thinking theorem, Theorem 5.5.5.

For the base case: let \(x=0\text{.}\) The left hand side is \(0^p =0\) and the right hand side is \(0\text{.}\) Since \(0 \equiv 0 \pmod{p}\) for all \(p\text{,}\) the base case is established.

For the inductive step we need to show if the statement is true for one value, say \(x=k\) then it is true for the next value \(k+1\text{.}\) That is, we need to show if \(k^p \equiv k \pmod{p}\) then \((k+1)^p \equiv k+1 \pmod{p}\text{.}\) To do this, we assume

\begin{equation*} k^p \equiv k \pmod{p} \end{equation*}

and examine

\begin{equation*} (k+1)^p \pmod{p}. \end{equation*}

By Theorem 5.5.5, we have

\begin{equation*} (k+1)^p \equiv k^p+1^p \pmod{p}\text{.} \end{equation*}

We can simplify \(1^p = 1\text{.}\) Then by the inductive hypothesis, we have

\begin{equation*} k^p \equiv k \pmod{p}\text{.} \end{equation*}

Combining those results gives,

\begin{equation*} (k+1)^p \equiv k^p+1^p \equiv k^p+1 \equiv k +1 \pmod{p}. \end{equation*}

Thus, by induction we have shown that \(x^p \equiv x \pmod{p}\) for all \(x \geq 0\text{.}\)

For the next part, we note that if \(\gcd(x,p)=1\) then \(x\) has a multiplicative inverse mod \(p\text{.}\) So we can multiply both sides of \(x^p \equiv x \pmod{p}\) by the multiplicative inverse of \(x\) to get \(x^{p-1} \equiv 1 \pmod{p}\text{.}\)