Divisibility and approximation

Remainders: write the base as $d \pm 1$

Expand $(d + 1)^n$:

Every term after the first is a multiple of $d$. So $(d + 1)^n$ leaves remainder $1$ when divided by $d$.

Now try $(d - 1)^n$. The expansion alternates in sign, and the last term is $(-1)^n$. All the other terms are multiples of $d$. So the remainder is $1$ when $n$ is even, and $d - 1$ when $n$ is odd. We add $d$ because a remainder cannot be negative.

Example. Find the remainder when $6^{83}$ is divided by $7$.

Step 1. Write the base. $6 = 7 - 1$, so $6^{83} = (7 - 1)^{83}$.

Step 2. Expand. $(7 - 1)^{83} = -1 + (\text{multiples of } 7)$, since $83$ is odd.

Step 3. Make the remainder positive. $-1 + 7 = 6$.

Answer: the remainder is $6$.

Going one step further: divide by $d^2$

Look at the expansion of $(d + 1)^n$ again. The terms from ${}^{n}C_{2}\,d^2$ onwards are all multiples of $d^2$. So when we divide by $d^2$, only the first two terms matter:

Example. Find the remainder when $11^{12}$ is divided by $100$.

Step 1. $11 = 10 + 1$, so $d = 10$ and $d^2 = 100$.

Step 2. $11^{12}$ leaves the same remainder as $1 + 12 \times 10 = 121$.

Step 3. $121$ divided by $100$ leaves $21$.

Answer: $21$. So $11^{12}$ ends in the digits $21$. Indeed $11^{12} = 3138428376721$.

Proving that a number is divisible

To show that an expression is divisible by $d$, write it as a sum of binomial terms and see what is left.

Example 1. Show that $9^n - 8n - 1$ is divisible by $64$.

Write $9^n = (1 + 8)^n = 1 + 8n + {}^{n}C_{2} \cdot 8^2 + {}^{n}C_{3} \cdot 8^3 + \cdots$. So

For $n = 3$: $729 - 24 - 1 = 704 = 64 \times 11$.

Example 2. Show that $10^n + 3 \cdot 4^{n + 2} + 5$ is divisible by $9$.

Step 1. $10^n = (9 + 1)^n = 1 + (\text{a multiple of } 9)$.

Step 2. $4^{n + 2} = (3 + 1)^{n + 2} = 1 + 3(n + 2) + (\text{a multiple of } 9)$. So $3 \cdot 4^{n + 2} = 3 + 9(n + 2) + (\text{a multiple of } 9)$.

Step 3. The total is $1 + 3 + 5 = 9$ plus a multiple of $9$. So it is divisible by $9$.

For $n = 1$: $10 + 192 + 5 = 207 = 9 \times 23$.

The last digits of a power

Example. Find the last two digits of $7^{82}$.

Step 1. Find a power close to a multiple of 100. $7^4 = 2401 = 2400 + 1$.

Step 2. Raise it. $7^{80} = (2401)^{20} = (1 + 2400)^{20} = 1 + 20 \times 2400 + \cdots$. Every term after the first is a multiple of $100$. So $7^{80}$ ends in $01$.

Step 3. Finish. $7^{82} = 7^{80} \times 49$, which ends in $01 \times 49$, that is, $49$.

Answer: the last two digits are $49$.

Approximating a power

Write $(1 + h)^n$ as a sum:

When $h$ is small, $h^2$ is much smaller, $h^3$ smaller still. So the first few terms are almost the whole answer.

Example 1. Estimate $1.01^{10}$. Here $h = 0.01$ and $n = 10$:

The exact value is $1.10462\ldots$

Example 2. Estimate $0.99^{6}$. Write $0.99 = 1 - 0.01$, so $h = -0.01$:

The exact value is $0.94148\ldots$

The error is about the size of the first term we left out. For $1.01^{10}$ that term is ${}^{10}C_{3} \times 0.01^3 = 0.00012$, and the error is $0.000122$.

Make $h$ larger and the dots spread out. The method works well only when $h$ is small.

Practise with new numbers

Try it in Python

The program shows that $11^{12}$ and $1 + 12 \times 10$ leave the same remainder on division by $100$. Then it finds the last two digits of $7^{82}$. Last, it adds the first terms of $1.01^{10}$ one at a time.

Common mistakes

• Leaving a negative remainder. With $(d - 1)^n$ and $n$ odd, the remainder is $d - 1$, not $-1$.
• Mixing up the sign of $h$. For $0.99^6$ use $h = -0.01$. The terms with odd powers of $h$ are then negative.
• Using the approximation when $h$ is not small. The dots in the simulation move away from the line as $h$ grows.
• Dividing by $d$ when you meant $d^2$. Two terms of $(d + 1)^n$ survive division by $d^2$, but only one survives division by $d$.
• Starting from the wrong power of $10$. For the last two digits, look for a power that is $1$ more than a multiple of $100$.

Remember these

• $(d + 1)^n$ leaves remainder $1$ when divided by $d$.
• $(d - 1)^n$ leaves remainder $1$ if $n$ is even, and $d - 1$ if $n$ is odd.
• $(d + 1)^n \equiv 1 + n\,d \pmod{d^2}$.
• To prove divisibility, write each power as $(\text{multiple} \pm 1)^n$ and expand.
• For small $h$, $(1 + h)^n \approx 1 + nh + {}^{n}C_{2}\,h^2$.
• The error is about the size of the first term left out.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

1. Find the remainder when $10^{20}$ is divided by $9$.

2. Find the remainder when $13^{23}$ is divided by $14$.

3. Find the last two digits of $51^{9}$.

4. Use two terms to estimate $1.02^{5}$.

5. Find the remainder when $7^{20}$ is divided by $6$.