5.3 Divisibility statements and other proofs using PMI
There is a very famous result known as Fermat’s Little Theorem. This would probably be abbreviated FLT except for two things. In science fiction, FLT means “faster than light travel” and there is another theorem due to Fermat that goes by the initials FLT: Fermat’s Last Theorem. Fermat’s last theorem states that equations of the form \(a^n+b^n=c^n\), where \(n\) is a positive natural number, only have integer solutions that are trivial (like \(0^3+1^3=1^3\)) when \(n\) is greater than 2. When \(n\) is 1, there are lots of integer solutions. When \(n\) is 2, there are still plenty of integer solutions — these are the so-called Pythagorean triples, for example 3,4 & 5 or 5,12 & 13. It is somewhat unfair that this statement is known as Fermat’s last theorem since he didn’t prove it (or at least we can’t be sure that he proved it). Five years after his death, Fermat’s son published a translated47 version of Diophantus’s Arithmetica containing his father’s notations. One of those notations — near the place where Diophantus was discussing the equation \(x^2+y^2=z^2\) and its solution in whole numbers — was the statement of what is now known as Fermat’s last theorem as well as the following claim:
Cuius rei demonstrationem mirabilem sane detexi hanc marginis exiguitas non caperet.
In English:
I have discovered a truly remarkable proof of this that the margin of this page is too small to contain.
Between 1670 and 1994 a lot of famous mathematicians worked on FLT but never found the “demonstrationem mirabilem.” Finally in 1994, Andrew Wiles of Princeton announced a proof of FLT, but in Wiles’s own words, his is “a twentieth century proof” it can’t be the proof Fermat had in mind.
These days most people believe that Fermat was mistaken. Probably he thought a proof technique that works for small values of \(n\) could be generalized. It remains a tantalizing question, can a proof of FLT using only methods available in the 17th century be accomplished?
Part of the reason that so many people spent so much effort on FLT over the centuries is that Fermat had an excellent record as regards being correct about his theorems and proofs. The result known as Fermat’s little theorem is an example of a theorem and proof that Fermat got right. It is probably known as his “little” theorem because its statement is very short, but it is actually a fairly deep result.
A slight restatement of Fermat’s little theorem is that \(p\) is always a divisor of \(x^p-x\) (assuming \(p\) is a prime and \(x\) is an integer). Math professors enjoy using their knowledge of Fermat’s little theorem to cook up divisibility results that can be proved using mathematical induction. For example, consider the following:
\[ \forall n \in {\mathbb N}, 3 \mid (n^3 + 2n + 6). \]
This is really just the \(p=3\) case of Fermat’s little theorem with a little camouflage added: \(n^3 + 2n + 6 = (n^3-n)+3(n+2)\). But let’s have a look at proving this statement using PMI.
Theorem 5.6 \(\forall n \in {\mathbb N}, 3 \mid (n^3 + 2n + 6)\)
Proof. (By mathematical induction)
Basis: Clearly \(3 \mid 6\).
Inductive step:
(We need to show that \(3 \mid (k^3 + 2k + 6) \; \implies \; 3 \mid ((k+1)^3 + 2(k+1) + 6\).)
Note that \[\begin{gather*} (k+1)^3 + 2(k+1) + 6 \\ = (k^3 + 3k^2 + 3k + 1) + (2k + 2) + 6\\ = (k^3 + 2k + 6) + 3k^2 + 3k + 3\\ = (k^3 + 2k + 6) + 3(k^2 + k + 1). \end{gather*}\]
By the inductive hypothesis, 3 is a divisor of \(k^3 + 2k + 6\) so there is an integer \(m\) such that \(k^3 + 2k + 6 = 3m\). Thus,
\[\begin{gather*} (k+1)^3 + 2(k+1) + 6 \\ = 3m + 3(k^2 + k + 1) \\ = 3(m + k^2 + k + 1). \end{gather*}\] This equation shows that 3 is a divisor of \((k+1)^3 + 2(k+1) + 6\), which is the desired conclusion.
Exercise 5.4 Devise an inductive proof of the statement, \(\forall n \in {\mathbb N}, 5 \mid n^5+4n-10\).
There is one other subtle trick for devising statements to be proved by PMI that you should know about. An example should suffice to make it clear. Notice that \(7\) is equivalent to \(1 \pmod{6}.\) It follows that any power of \(7\) is also \(1 \pmod{6}\). So, if we subtract \(1\) from some power of 7 we will have a number that is divisible by \(6\).
The proof (by PMI) of a statement like this requires another subtle little trick. Somewhere along the way in the proof you’ll need the identity \(7=6+1\).
Theorem 5.7 \[ \forall n \in {\mathbb N}, \; 6 \mid 7^n-1 \]
Proof. (By PMI)
Basis: Note that \(7^0-1\) is \(0\) and also that \(6 \mid 0\).
Inductive step:
(We need to show that if \(6 \mid 7^k-1\) then \(6 \mid 7^{k+1}-1\).)
Note that \[\begin{gather*} 7^{k+1}-1 = 7 \cdot 7^k -1 \\ = (6 + 1) \cdot 7^k - 1 \\ = 6 \cdot 7^k + 1 \cdot 7^k - 1\\ = 6(7^k) + (7^k - 1) \end{gather*}\]
By the inductive hypothesis, \(6 \mid 7^k - 1\) so there is an integer \(m\) such that \(7^k - 1 = 6m\). It follows that
\[ 7^{k+1}-1 = 6(7^k) + 6m. \]
So, clearly, \(6\) is a divisor of \(7^{k+1}-1\).
Mathematical induction can often be used to prove inequalities. There are quite a few examples of families of statements where there is an inequality for every natural number. Often such statements seem to be obviously true and yet devising a proof can be illusive. If such is the case, try using PMI. One hint: it is fairly typical that the inductive step in a PMI proof of an inequality will involve reasoning that isn’t particularly sharp. Just remember that if you have an inequality and you make the big side even bigger, the resulting statement is certainly still true!
Consider the sequences \(2^n\) and \(n!\): \[\begin{array}{c|ccccc} n & 0 & 1 & 2 & 3 & \ldots \\ \hline 2^n & 1 & 2 & 4 & 8 & \ldots \\ \hline n! & 1 & 1 & 2 & 6 & \ldots \\ \end{array}\]
As the table illustrates, \(2^n > n!\) for small values of \(n\). But from \(n=4\) onward the inequality is reversed.
Theorem 5.8 \[ \forall n \geq 4 \in {\mathbb N}, 2^n < n! \]
Proof. (By mathematical induction)
Basis: When \(n=4\) we have \(2^4 < 4!\), which is certainly true (\(16 < 24\)).
Inductive step: Suppose that \(k\) is a natural number with \(k > 4\), and that \(2^k < k!\). Multiply the left hand side of this inequality by \(2\) and the right hand side by \(k+1\)48 to get \[ 2\cdot 2^{k} < (k+1) \cdot k!. \]
So \[ 2^{k+1} < (k+1)!. \]
The observant calculus student will certainly be aware of the fact that, asymptotically, exponential functions grow faster than polynomial functions. That is, if you have a base \(b\) which is greater than 1, the function \(b^x\) is eventually larger than any polynomial \(p(x)\). This may seem a bit hard to believe if \(b=1.001\) and \(p(x) = 500x^{10}\). The graph of \(y=1.001^x\) is practically indistinguishable from the line \(y=1\) (at first), whereas the graph of \(y=500x^{10}\) has already reached the astronomical value of five trillion (\(5,000,000,000,000\)) when \(x\) is just \(10\). Nevertheless, the exponential will eventually outstrip the polynomial. We can use the methods of this section to get started on proving the fact mentioned above. Consider the two sequences \(n^2\) and \(2^n\).
\[\begin{array}{c|ccccccc} n & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline n^2 & 0 & 1 & 4 & 9 & 16 & 25 & 36 \\ \hline 2^n & 1 & 2 & 4 & 8 & 16 & 32 & 64 \\ \end{array}\]
If we think of a “race” between the sequences \(n^2\) and \(2^n\), notice that \(2^n\) starts out with the lead. The two sequences are tied when \(n=2\). Briefly, \(n^2\) goes into the lead but they are tied again when \(n=4\). After that it would appear that \(2^n\) recaptures the lead for good. Of course we’re making a rather broad presumption — is it really true that \(n^2\) never catches up with \(2^n\) again? Well, if we’re right, then the following theorem should be provable:
Theorem 5.9 For all natural numbers \(n\), if \(n \geq 4\) then \(n^2 \leq 2^n\).
Basis: When \(n=4\) we have \(4^2 \leq 2^4\), which is true since both numbers are 16.
Inductive step:
(We assume that \(k^2 \leq 2^k\) and then show that \((k+1)^2 \leq 2^{k+1}\).)
The inductive hypothesis tells us that
\[ k^2 \leq 2^k. \]
If we add \(2k+1\) to the left-hand side of this inequality and \(2^k\) to the right-hand side we will produce the desired inequality. Thus our proof will follow provided that we know that \(2k+1 \leq 2^k\). Indeed, it is sufficient to show that \(2k+1 \leq k^2\) since we already know (by the inductive hypothesis) that \(k^2 \leq 2^k\).
So the result remains in doubt unless you can complete the exercise that follows…
5.3.1 Exercises
Give inductive proofs of the following
\(\forall x \in {\mathbb N}, \; 3 \!\mid\!x^3-x\)
\(\forall x \in {\mathbb N}, \; 3 \!\mid\!x^3+5x\)
\(\forall x \in {\mathbb N}, \; 11 \!\mid\!x^{11}+10x\)
\(\forall n \in {\mathbb N}, \; 3 \!\mid\!4^n-1\)
\(\forall n \in {\mathbb N}, \; 6 \!\mid\!(3n^{2}+3n-12)\)
\(\forall n \in {\mathbb N}, \; 5 \!\mid\!(n^{5}-5n^{3}+14n)\)
\(\forall n \in {\mathbb N}, \; 4 \!\mid\!(13^{n}+4n-1)\)
\(\forall n \in {\mathbb N}, \; 7 \!\mid\!8^n+6\)
\(\forall n \in {\mathbb N}, \; 6 \!\mid\!2n^3 - 2n - 12\)
\(\forall n \geq 3 \in {\mathbb N}, \; 3n^2+3n+1 < 2n^3\)
\(\forall n > 3 \in {\mathbb N}, \; n^3 < 3^n\)
\(\forall n \geq 3 \in {\mathbb N}, \; n^{3}+3>n^{2}+3n+1\)
\(\forall x \geq 4 \in {\mathbb N}, \; x^22^x \leq 4^x\)