Proving divisibility

Is $7^n - 1$ always divis­i­ble by 6? For $n = 1, 2, 3$ the val­ues are 6, 48 and 342, and each is a mul­ti­ple of 6. Induc­tion can prove that this goes on for ever. Divis­i­bil­ity proofs need one extra trick in the induc­tive step: rewrite the $(k + 1)$ expres­sion so that the $k$ expres­sion appears inside it. This les­son shows the trick and prac­tises it on sev­eral types.

What "divis­i­ble" means in a proof#

A whole num­ber $N$ is divis­i­ble by $m$ when $N = m \times q$ for some whole num­ber $q$. In a proof we use this as an equa­tion. So the hypoth­e­sis "$7^k - 1$ is divis­i­ble by 6" is writ­ten

$$7^k - 1 = 6q \quad \text{for some whole number } q$$

and then we can replace $7^k$ by $6q + 1$ wher­ever it is use­ful.

We also use two sim­ple facts: a sum of mul­ti­ples of $m$ is a mul­ti­ple of $m$, and any mul­ti­ple of a mul­ti­ple of $m$ is a mul­ti­ple of $m$.

Exam­ple 1#

Prove that $7^n - 1$ is divis­i­ble by 6 for every nat­ural num­ber $n$.

Base step. For $n = 1$: $7 - 1 = 6$, which is divis­i­ble by 6.

Hypoth­e­sis. Assume $7^k - 1 = 6q$ for some whole num­ber $q$. Then $7^k = 6q + 1$.

Induc­tive step. We must show that $7^{k+1} - 1$ is divis­i­ble by 6.

$$7^{k+1} - 1 = 7 \cdot 7^k - 1 = 7(6q + 1) - 1 = 42q + 6 = 6(7q + 1)$$

Since $7q + 1$ is a whole num­ber, $7^{k+1} - 1$ is divis­i­ble by 6.

Con­clu­sion. By induc­tion, $7^n - 1$ is divis­i­ble by 6 for all nat­ural num­bers $n$.

A sec­ond way: add and sub­tract#

Instead of sub­sti­tut­ing, you can make the $k$ expres­sion appear by adding and sub­tract­ing a suit­able term. In Exam­ple 1:

$$7^{k+1} - 1 = 7 \cdot 7^k - 7 + 7 - 1 = 7(7^k - 1) + 6$$

The first part is 7 times a mul­ti­ple of 6, and the sec­ond part is 6. Both meth­ods are fine; use whichever you find clearer.

Exam­ple 2#

Prove that $3^{2n} - 1$ is divis­i­ble by 8 for every nat­ural num­ber $n$.

Base step. For $n = 1$: $3^2 - 1 = 8$. True.

Hypoth­e­sis. Assume $3^{2k} - 1 = 8q$, so $3^{2k} = 8q + 1$.

Induc­tive step. Note that $3^{2(k+1)} = 3^{2k + 2} = 9 \cdot 3^{2k}$. So

$$3^{2(k+1)} - 1 = 9(8q + 1) - 1 = 72q + 8 = 8(9q + 1)$$

which is divis­i­ble by 8. By induc­tion the result holds for all $n$.

Exam­ple 3#

Prove that $n^3 - n$ is divis­i­ble by 6 for every nat­ural num­ber $n$.

Base step. For $n = 1$: $1 - 1 = 0 = 6 \times 0$, which is divis­i­ble by 6.

Hypoth­e­sis. Assume $k^3 - k$ is divis­i­ble by 6.

Induc­tive step. Expand:

$$(k + 1)^3 - (k + 1) = k^3 + 3k^2 + 3k + 1 - k - 1 = (k^3 - k) + 3k(k + 1)$$

The first bracket is divis­i­ble by 6 by the hypoth­e­sis. In the sec­ond part, $k(k + 1)$ is a prod­uct of two con­sec­u­tive whole num­bers, so one of them is even and $k(k + 1)$ is even; there­fore $3k(k + 1)$ is divis­i­ble by $3 \times 2 = 6$. The sum of two mul­ti­ples of 6 is a mul­ti­ple of 6. By induc­tion the result holds for all $n$.

Exam­ple 4#

Prove that $4^n + 15n - 1$ is divis­i­ble by 9 for every nat­ural num­ber $n$.

Base step. For $n = 1$: $4 + 15 - 1 = 18 = 9 \times 2$. True.

Hypoth­e­sis. Assume $4^k + 15k - 1 = 9q$, so $4^k = 9q - 15k + 1$.

Induc­tive step.

$$\begin{aligned} 4^{k+1} + 15(k + 1) - 1 &= 4 \cdot 4^k + 15k + 14 \\ &= 4(9q - 15k + 1) + 15k + 14 \\ &= 36q - 60k + 4 + 15k + 14 \\ &= 36q - 45k + 18 \\ &= 9(4q - 5k + 2) \end{aligned}$$

which is divis­i­ble by 9. By induc­tion the result holds for all $n$.

Exam­ple 5#

Prove that $x^n - y^n$ is divis­i­ble by $x - y$ for every nat­ural num­ber $n$, where $x$ and $y$ are whole num­bers with $x \neq y$.

Base step. For $n = 1$: $x - y$ is divis­i­ble by itself.

Hypoth­e­sis. Assume $x^k - y^k = (x - y)q$ for some whole num­ber $q$.

Induc­tive step. Add and sub­tract $xy^k$:

$$x^{k+1} - y^{k+1} = x^{k+1} - xy^k + xy^k - y^{k+1} = x(x^k - y^k) + y^k(x - y) = (x - y)(xq + y^k)$$

which is divis­i­ble by $x - y$. By induc­tion the result holds for all $n$.

This one result con­tains many oth­ers. With $x = 7$, $y = 1$ it says $7^n - 1$ is divis­i­ble by 6 (Exam­ple 1); with $x = 9$, $y = 1$ it says $9^n - 1 = 3^{2n} - 1$ is divis­i­ble by 8 (Exam­ple 2).

Exam­ple 6#

Prove that $2^{3n} - 1$ is divis­i­ble by 7 for every nat­ural num­ber $n$.

Base step. $2^3 - 1 = 7$. True.

Hypoth­e­sis. Assume $2^{3k} - 1 = 7q$, so $2^{3k} = 7q + 1$.

Induc­tive step. $2^{3(k+1)} - 1 = 8 \cdot 2^{3k} - 1 = 8(7q + 1) - 1 = 56q + 7 = 7(8q + 1)$. By induc­tion the result holds for all $n$.

Prac­tice#

Prove each state­ment by induc­tion for every nat­ural num­ber $n$.

1. $5^n - 1$ is divis­i­ble by 4.
2. $11^n - 1$ is divis­i­ble by 10.
3. $3^{2n} + 7$ is divis­i­ble by 8.
4. $n(n + 1)(n + 2)$ is divis­i­ble by 6.
5. $6^n + 4$ is divis­i­ble by 5.
6. $3^n + 7^n - 2$ is divis­i­ble by 8.
7. $5^{2n} - 1$ is divis­i­ble by 24.
8. $10^n + 3 \cdot 4^{n+2} + 5$ is divis­i­ble by 9.

Answers#

In each answer the base step and the key line of the induc­tive step are given.

1. Base: $5 - 1 = 4$. Step: if $5^k = 4q + 1$, then $5^{k+1} - 1 = 5(4q + 1) - 1 = 4(5q + 1)$.
2. Base: $11 - 1 = 10$. Step: if $11^k = 10q + 1$, then $11^{k+1} - 1 = 11(10q + 1) - 1 = 10(11q + 1)$.
3. Base: $9 + 7 = 16$. Step: if $3^{2k} = 8q - 7$, then $3^{2k+2} + 7 = 9(8q - 7) + 7 = 72q - 56 = 8(9q - 7)$.
4. Base: $1 \times 2 \times 3 = 6$. Step: $(k + 1)(k + 2)(k + 3) = k(k + 1)(k + 2) + 3(k + 1)(k + 2)$; the first part is a mul­ti­ple of 6 by the hypoth­e­sis, and $(k + 1)(k + 2)$ is even, so the sec­ond part is a mul­ti­ple of 6.
5. Base: $6 + 4 = 10$. Step: if $6^k = 5q - 4$, then $6^{k+1} + 4 = 6(5q - 4) + 4 = 30q - 20 = 5(6q - 4)$.
6. Base: $3 + 7 - 2 = 8$. Step: $3^{k+1} + 7^{k+1} - 2 = 3(3^k + 7^k - 2) + 4 \cdot 7^k + 4 = 3(3^k + 7^k - 2) + 4(7^k + 1)$, and $7^k + 1$ is even because $7^k$ is odd, so $4(7^k + 1)$ is a mul­ti­ple of 8.
7. Base: $25 - 1 = 24$. Step: if $5^{2k} = 24q + 1$, then $5^{2k+2} - 1 = 25(24q + 1) - 1 = 24(25q + 1)$.
8. Base: $10 + 3 \times 64 + 5 = 207 = 9 \times 23$. Step: $10^{k+1} + 3 \cdot 4^{k+3} + 5 = 10\left(10^k + 3 \cdot 4^{k+2} + 5\right) - 18 \cdot 4^{k+2} - 45$, and $18 \cdot 4^{k+2} + 45 = 9\left(2 \cdot 4^{k+2} + 5\right)$ is a mul­ti­ple of 9.