## Divisible By 11

#### Problem

Consider the following results.

10^{1} + 1 = 11

10^{2} 1 = 99 = 9 11

10^{3} + 1 = 1001 = 91 11

10^{4} 1 = 9999 = 909 11

10^{5} + 1 = 100001 = 9091 11

Prove that 10^{n}1 is divisible by 11 if `n` is even and 10^{n}+1 is divisible by 11 if `n` is odd.

#### Solution

As (`x`1)^{n} = (`x`1)(`x`^{n1} + `x`^{x2} + ... + 1), we get:

10^{2k}1 = 100^{k}1 = (1001)(100^{k1} + ... + 1) = 99Q 0 mod 11.

That is, 10^{n}1 is divisible by 11 if `n` is even.

As 10^{2k} 1 mod 11, we can multiply both sides of the congruence by 10 to obtain 10^{2k+1} 10 -1 mod 11; that is, 10^{2k+1}+1 0 mod 11.

Hence we prove that 10^{n}+1 is divisible by 11 if `n` is odd.

Prove that 100^{n}+1 is divisible by 101 iff `n` is odd, 1000^{n}+1 is divisible by 1001 iff `n` is odd.

What about 10000^{n}+1? Generalise.

Problem ID: 208 (17 Feb 2005) Difficulty: 3 Star