# Divisibility tests and remainder mod $9,11,99,101,999,1001\,$ (casting out nines and elevens)

Now I have proved the following two problems:

(1) Prove that a number and the sum of its digits have the same remainder upon division by 9. (2) Given an integer, consider the difference between the sum of the digits in odd positions (counting from the right) and those in even positions. Show that the difference has the same remainder as the number itself when divided by 11.

Then, I need help on the following problem:

Partition the digits of a number into groups of two and three, respectively, starting from the right. Treat these as two- and three-digit numbers, respectively, and proceed similarly as in the two problems above. What divisibility rules arise?

Let's look at a proof of (1) again.

The key is that $10 \equiv 1 \pmod 9$. If we write the number $$n = a_k 10^k + a_{k-1}10^{k-1} + \ldots + a_0 = a_k a_{k-1} \ldots a_0,$$ where the last expression is digit-by-digit and not multiplication and $0 \leq a_i < 10$, then we get that $$a_k a_{k-1} \ldots a_0 \pmod 9$$ is the same as $$a_k 10^k + a_{k-1}10^{k-1} + \ldots + a_0 = a_k a_{k-1} \ldots a_0 \equiv a_k + a_{k-1} + \ldots + a_0 \pmod 9,$$

which is the statement we were asked to prove. But they key was that $10 \equiv 1 \pmod 9$, and that we happen to write in a base-10 system, so that the way we express each digit is with a power of $10$ in front of it. The exact same proof works for remainders upon division by $3$, since $10 \equiv 1 \pmod 3$ too.

Now suppose we don't break our number into one-digit blocks, but instead two-digit blocks. We are essentially using a base-100 system now, as silly as that sounds. Before, the key was that $10 \equiv 1 \mod m$. For what $m$ is $100 \equiv 1 \mod m$? Answer: when $m = 3, 9, 11$, i.e. the factors of $99$. (If you know the Chinese Remainder Theorem or have done enough arithmetic to get a good intuition, this may feel very obvious).

So I claim that writing

$$n = b_k 100^k + b_{k-1}100^{k-1} + \ldots + b_0,$$

where this time each $b_i$ satisfies $0 \leq b_i < 100$ (i.e. we split the number into 2-digit chunks), then $n \equiv \sum b_i \pmod{m}$, where $m = 3,9,$ or $11$. Why? Let's check to make sure we understand. We'll check with $11$. We know that $100 \equiv 1 \pmod{11}$, so that $100^k \equiv 1 \pmod{11}$. Then

$$b_k 100^k + b_{k-1}100^{k-1} + \ldots + b_0 \equiv b_k + b_{k-1} + \ldots + b_0 \pmod{11}.$$

And so we have it, and we've developed an easier-to-compute-maybe divisibility test.

The key part for the alternating sum in (2) is that $10 \equiv -1 \pmod{11}$, so that if

$$n = a_k 10^k + a_{k-1}10^{k-1} + \ldots + a_0,$$

then $n \equiv a_0 - a_1 + a_2 - \ldots + (-1)^k a_k \pmod{11}$. So for two-digit chunks in an effective base-100 system, we get the same sort of behavior for the divisors of $101$. But wouldn't you know - $101$ is prime. So all we can conclude that $n \equiv \sum (-1)^jb_j \pmod {101}$.

Similarly, for 3-digit splits, we can conclude that for the factors $m$ of $999$, $n \equiv \sum c_j \pmod m$, and for the factors $d$ of $1001$, $n \equiv \sum (-1)^j c_j \pmod d$. (I continue my pattern, $c_j$ comes from three-digit blocks).

In fact, I happen to know that $1001 = 7 \cdot 11 \cdot 13$, and the take-alternating-sum-and-difference-of-three-digit-blocks is actually how I quickly decide if a number is divisible by $7, 11, 13$ all the time.