Lesson 4: Proving divisibility by induction

Why the digit test for 9 works

SkillProving divisibility by induction

Worked example

  • Complex unfamiliar
  • Technology free

(a) Prove by mathematical induction that 10n−110^n - 1 is divisible by 99 for all n∈Z+n \in \mathbb{Z}^+.

(b) A three-digit number with digits aa, bb and cc equals 100a+10b+c100a + 10b + c. Use part (a) to show that it is divisible by 99 exactly when a+b+ca + b + c is divisible by 99.

1 of 6 steps
  1. Step 1: (a) Initial statement

    Let P(n)P(n) be the statement "10n−110^n - 1 is divisible by 99". When n=1n = 1: 10−1=9=9×110 - 1 = 9 = 9 \times 1, so P(1)P(1) is true.

Try a similar one

A fresh question of the same kind, checked as you answer, with hints and a full solution.

Method

  1. Prove the divisibility result by induction.

  2. Split each power of 1010 into (10n−1)+1(10^n - 1) + 1.

  3. Use the result to show the difference is a multiple of the divisor.

Watch out for

  • In (b), checking a few numbers is not a proof. You need the algebraic split, which works for every choice of digits.

Save your progress with a free account