Divisibility by induction

What this les­son cov­ers#

Induc­tion is not only for sums. It also proves that an expres­sion such as $4^n - 1$ is divis­i­ble by some num­ber for every $n$. This les­son shows how to find the divi­sor, lists the stan­dard divis­i­bil­ity results, and intro­duces con­gru­ence nota­tion.

Find­ing the divi­sor#

To find the num­ber that divides a given expres­sion for all $n$, put $n = 1$ and $n = 2$ in the expres­sion and com­pute the two val­ues. Their G.C.D. (H.C.F.) gives the required divi­sor. Induc­tion then proves the divis­i­bil­ity for every $n$.

How the induc­tive step works#

Sup­pose we want to show $m$ divides $f(n)$. Assume $f(k) = m\lambda$ for some inte­ger $\lambda$. Write $f(k+1)$ so that $f(k)$ appears inside it, replace $f(k)$ by $m\lambda$, and show that what remains is also a mul­ti­ple of $m$.

Exam­ple 1#

Show that $4^n - 1$ is divis­i­ble by $3$ for all $n \in \mathbb{N}$.

For $n = 1$: $4 - 1 = 3$, divis­i­ble by $3$. Assume $4^k - 1 = 3\lambda$, so $4^k = 3\lambda + 1$. Then

$$\begin{aligned} 4^{k+1} - 1 &= 4\cdot 4^k - 1 \\ &= 4(3\lambda + 1) - 1 \\ &= 12\lambda + 3 \\ &= 3(4\lambda + 1), \end{aligned}$$

which is divis­i­ble by $3$. Hence the result is true for all $n$.

Exam­ple 2#

Find the num­ber that divides $2\cdot 7^n + 3\cdot 5^n - 5$ for all $n \in \mathbb{N}$.

For $n = 1$ the value is $14 + 15 - 5 = 24$. For $n = 2$ it is $98 + 75 - 5 = 168$. The G.C.D. of $24$ and $168$ is $24$, so the expres­sion is divis­i­ble by $24$. (Induc­tion con­firms it for all $n$.)

Stan­dard divis­i­bil­ity results#

1. The sum of the cubes of three con­sec­u­tive nat­ural num­bers is always divis­i­ble by $9$.
2. For all pos­i­tive inte­gers $n$, $x^n - y^n$ is divis­i­ble by $x - y$.
3. For all pos­i­tive inte­gers $n$, $x^{2n+1} + y^{2n+1}$ is divis­i­ble by $x + y$. (An odd power sum always has the fac­tor $x+y$.)
4. For all pos­i­tive inte­gers $n$, $x^{2n-1} + y^{2n-1}$ is divis­i­ble by $x + y$. This is the same fact as result 3, indexed from $n = 1$.
5. $P^{n+1} + (P+1)^{2n-1}$ is divis­i­ble by $P^2 + P + 1$. It holds for every $n \in \mathbb{N}$.
6. If $p$ is a prime, then $n^p - n$ is divis­i­ble by $p$ for every nat­ural num­ber $n$ (Fer­mat's lit­tle the­o­rem).
7. If $n$ is any odd inte­ger, then $n(n^2 - 1)$ is divis­i­ble by $24$.
8. The prod­uct of $n$ con­sec­u­tive nat­ural num­bers is always divis­i­ble by $n!$.

For exam­ple, result 2 shows at once that $5^n - 2^n$ is divis­i­ble by $3$, and result 7 gives $5\cdot 24 = 120$, a mul­ti­ple of $24$.

Con­gru­ence mod­ulo $m$#

If $x, y, m$ are pos­i­tive inte­gers, then $x$ is said to be con­gru­ent to $y$ mod­ulo $m$ if $x - y$ is divis­i­ble by $m$. This is writ­ten

$$x \equiv y \pmod{m}.$$

For exam­ple, $17 \equiv 5 \pmod{4}$ because $17 - 5 = 12$ is divis­i­ble by $4$. The divis­i­bil­ity state­ments above can all be writ­ten this way: "$4^n - 1$ is divis­i­ble by $3$" is the same as $4^n \equiv 1 \pmod 3$.

Prac­tice#

1. Prove by induc­tion that $3^{2n} - 1$ is divis­i­ble by $8$.
2. Prove by induc­tion that $7^n - 3^n$ is divis­i­ble by $4$.
3. Find the largest num­ber that divides $5^n - 1$ for all $n \in \mathbb{N}$ using the val­ues at $n = 1, 2$.
4. Using the G.C.D. method, find the num­ber that divides $49^n + 16n - 1$ for all $n$.
5. Is $23 \equiv 8 \pmod 5$? Give the rea­son.
6. Prove that $49^n + 16n - 1$ is divis­i­ble by $64$.

Answers#