Induction and Divisibility

Turning Divisibility into an Induction Claim

In the previous tutorial, induction was used to prove identities involving finite products. The same proof structure applies to divisibility: instead of showing that two expressions are equal, we show that one integer is an integer multiple of another. The key is to make the inductive step preserve that multiple.

For example, a claim that \(4\) divides \(5^n-1\) means that \(5^n-1\) can be written as \(4\) times an integer. To pass from \(n\) to \(n+1\), we use \(5^{n+1}=5\cdot5^n\) to relate the new expression to the old one. The inductive hypothesis then supplies the multiple of \(4\) needed in the new case.

Definition (Divisibility). For integers \(d\) and \(a\), we say that \(d\) divides \(a\), written \(d\mid a\), if there is an integer \(q\) such that \(a=dq\). In this case, \(d\) is a divisor of \(a\), and \(a\) is a multiple of \(d\).

The integer \(q\) in the definition is sometimes called a quotient or a witness to the divisibility. The definition asks for an integer \(q\), not merely a real number. For instance, \(3\mid 12\) because \(12=3\cdot4\), whereas \(3\nmid 14\) because there is no integer \(q\) with \(14=3q\).

A Useful Rule for Divisibility

The algebra in an induction proof often combines the expression in the inductive hypothesis with another term. The following rule explains why such combinations preserve divisibility.

Lemma (Integer linear combinations preserve divisibility). If \(d\mid a\) and \(d\mid b\), where \(d,a,b\in\mathbb{Z}\), then \(d\mid ra+sb\) for all integers \(r\) and \(s\).

Proof. Since \(d\mid a\), there is an integer \(u\) such that \(a=du\). Since \(d\mid b\), there is an integer \(v\) such that \(b=dv\). Therefore

$$ ra+sb=r(du)+s(dv)=d(ru+sv). $$

Because \(r,s,u,v\) are integers, \(ru+sv\) is an integer. Thus \(ra+sb\) is an integer multiple of \(d\), which proves \(d\mid ra+sb\). \(\square\)

In particular, if \(d\mid a\), then \(d\mid ra\) for every integer \(r\); and if \(d\mid a\) and \(d\mid b\), then \(d\mid a+b\) and \(d\mid a-b\). These consequences are often the entire algebraic justification needed in an inductive step.

A Divisibility Claim About Powers

Consider the claim that \(4\mid 5^n-1\) for every \(n\in\mathbb{N}_0\). The index begins at \(0\), so the base case must check \(n=0\). In the inductive step, the useful rearrangement is to express the new difference as five times the old difference, plus \(4\).

Theorem. For every \(n\in\mathbb{N}_0\), \(4\mid 5^n-1\).

Proof. Let \(P(n)\) be the statement \(4\mid 5^n-1\). At \(n=0\),

5^0-1=1-1=0=4\cdot0,

so \(P(0)\) is true. Now suppose \(P(n)\) is true for some \(n\in\mathbb{N}_0\). By the definition of divisibility, there is an integer \(q\) such that \(5^n-1=4q\). Then

5^{n+1}-1 = 5\cdot5^n-1 = 5(5^n-1)+4 = 5(4q)+4 = 4(5q+1).

Since \(5q+1\) is an integer, \(4\mid 5^{n+1}-1\). Thus \(P(n)\) implies \(P(n+1)\). The Principle of Mathematical Induction proves the claim for every \(n\in\mathbb{N}_0\). \(\square\)

Worked Example: Applying the Power Divisibility Result

The theorem immediately shows that \(4\mid 5^6-1\). To identify the integer quotient, calculate:

5^6-1=15625-1=15624=4\cdot3906.

The quotient \(3906\) is an integer, as divisibility requires. The inductive proof establishes the result for every nonnegative exponent without requiring a separate calculation of \(5^n\) for each \(n\). The base case is essential: at \(n=0\), the expression is \(0\), which is divisible by \(4\) because \(0=4\cdot0\).

Using a Difference to Prove Divisibility

For polynomial expressions, it is useful to compare the expression at \(n+1\) with the expression at \(n\). If their difference is a multiple of \(d\), then divisibility at \(n\) can be carried forward to \(n+1\). The algebraic difference should be computed explicitly; assuming it is divisible by \(d\) without checking it is a common source of errors.

Theorem. For every \(n\in\mathbb{N}_0\), \(3\mid n^3-n\).

Proof. Let \(P(n)\) be the statement \(3\mid n^3-n\). At \(n=0\), \(0^3-0=0=3\cdot0\), so \(P(0)\) holds. Suppose \(P(n)\) holds. Then \(n^3-n=3q\) for some integer \(q\). Compare the expression at \(n+1\) with the one at \(n\):

\begin{aligned} \bigl((n+1)^3-(n+1)\bigr)-(n^3-n) &=n^3+3n^2+3n+1-n-1-n^3+n\\ &=3n^2+3n\\ &=3n(n+1). \end{aligned}

Rearranging this equality and using the inductive hypothesis gives

(n+1)^3-(n+1) = (n^3-n)+3n(n+1) = 3q+3n(n+1) = 3\bigl(q+n(n+1)\bigr).

The quantity \(q+n(n+1)\) is an integer, so \(3\mid (n+1)^3-(n+1)\). This proves the inductive step. By the Principle of Mathematical Induction, \(3\mid n^3-n\) for every \(n\in\mathbb{N}_0\). \(\square\)

Worked Example: Checking a Cubic Divisibility Claim

Take \(n=5\). The theorem says that \(5^3-5\) is divisible by \(3\), and direct calculation verifies the quotient:

5^3-5=125-5=120=3\cdot40.

The expression at the next integer can also be checked using the difference from the proof. At \(n=5\), that difference is \(3\cdot5\cdot6=90\), so

6^3-6=(5^3-5)+90=120+90=210=3\cdot70.

The calculation illustrates the inductive mechanism: the new value is the previous value plus a multiple of \(3\). It is the general algebraic identity for the difference, rather than these particular numerical checks, that proves the claim for every index.

Three Consecutive Integers

A further example shows how to use a parity observation within an induction proof. The product of three consecutive integers is divisible by \(6\). For the inductive step, the difference between consecutive products is \(3\) times a product of two consecutive integers; that latter product is even.

Theorem. For every integer \(n\geq1\), \(6\mid n(n+1)(n+2)\).

Proof. At \(n=1\), the product is \(1\cdot2\cdot3=6=6\cdot1\), so the base case holds. Suppose \(6\mid n(n+1)(n+2)\). The difference between the product for \(n+1\) and the product for \(n\) is

\begin{aligned} (n+1)(n+2)(n+3)-n(n+1)(n+2) &=(n+1)(n+2)\bigl((n+3)-n\bigr)\\ &=3(n+1)(n+2). \end{aligned}

The integers \(n+1\) and \(n+2\) are consecutive, so one of them is even. Therefore \((n+1)(n+2)=2t\) for some integer \(t\), and the difference equals \(3(2t)=6t\). It is divisible by \(6\). By the inductive hypothesis, there is an integer \(q\) such that \(n(n+1)(n+2)=6q\). Hence

$$ (n+1)(n+2)(n+3) = n(n+1)(n+2)+3(n+1)(n+2) = 6q+6t = 6(q+t). $$

Since \(q+t\) is an integer, the new product is divisible by \(6\). Induction starting at \(n=1\) proves the theorem for every integer \(n\geq1\). \(\square\)

Worked Example: Divisibility of a Triple Product

For \(n=7\), the three consecutive integers are \(7,8,9\). Their product is

7\cdot8\cdot9=56\cdot9=504=6\cdot84.

The inductive step also explains how the next product relates to this one. The difference from \(7\cdot8\cdot9\) to \(8\cdot9\cdot10\) is

3\cdot8\cdot9=216=6\cdot36,

so \(8\cdot9\cdot10=504+216=720=6\cdot120\). Here the difference is divisible by \(6\) because the consecutive factors \(8\) and \(9\) include an even integer. This is exactly the feature used for every inductive step.

Choosing and Checking the Inductive Step

A divisibility statement is not proved merely by testing several values. A valid induction proof needs a correct base case and a step that works for an arbitrary index in the stated range. It also needs to show that the factor multiplying the divisor is an integer.

Write the claim as divisibility.
Specify the divisor and the index range, such as \(d\mid A_n\) for every \(n\geq m\).

Check the starting index.
Show directly that the starting expression equals the divisor times an integer.

Find a useful relation.
Rewrite \(A_{n+1}\) using \(A_n\), or calculate \(A_{n+1}-A_n\), looking for terms divisible by \(d\).

Use the inductive hypothesis.
Replace \(A_n\) by \(dq\) for an integer \(q\), then show that the resulting expression is still \(d\) times an integer.

Conclude for the full range.
Apply the Principle of Mathematical Induction, starting at the base index actually proved.

Pay particular attention to the index range. A claim beginning at \(n=1\) does not require a proof at \(n=0\), while a claim beginning at \(n=0\) does. Also, a difference divisible by \(d\) is useful only when it is correctly computed. In the triple-product proof, the difference is \(3(n+1)(n+2)\), and its divisibility by \(6\) depends on the fact that one of the two consecutive factors is even.

Key takeaway. To prove \(d\mid A_n\) by induction, establish divisibility at the base index and show that the expression at the next index is the earlier expression plus (or a suitable integer combination involving) a multiple of \(d\). Make the integer quotient explicit.

Check Your Understanding

Use the definition of divisibility and the induction arguments above to answer the following questions.

What does \(d\mid a\) mean in terms of an integer \(q\)?
If \(d\mid a\) and \(d\mid b\), why does \(d\mid 2a-3b\)?
In the proof that \(4\mid5^n-1\), what expression at index \(n+1\) is written using the expression at index \(n\)?
Compute \((n+1)^3-(n+1)-(n^3-n)\), and explain why it is divisible by \(3\).
Why is \(3(n+1)(n+2)\) divisible by \(6\) for every integer \(n\)?

What You'll Learn