Why does casting out $9$ and $11$ work to compute remainders?

Question

I found two examples that I'd like to understand:

Example 1: Find $112358132134 \mod 9$.

Solution is: $1+1+2+3+5+8+1+3+2+1+3+4 \mod 9 = 7 \mod 9 = 7$

Example 2: Find $62831853 \mod 11$.

Solution is: $(-6)+2+(-8)+3+(-1)+8+(-5)+3 \mod 11 = -4 \mod 11 = 7$

My question is: Based on what property we sum the digits of the number ( as Example 1) or subtract (as Example 2)?

Answer 1

Usually, we cannot compute the remainder of a number mod $n$ by summing the digits (example 1), or by subtracting alternately (example 2). This is a special trick that works for mod $9$ and $11$. It also works for mod $3$.

• To compute the remainder of a number mod $3$ or mod $9$, you may sum the digits and then compute the remainder of that result.

  Why it works: we write numbers in base $10$, and $10 \equiv 1$ mod $3$ or mod $9$, so multiplying by $10$ is really multiplying by $1$.

• To compute the remainder of a number mod $11$, you may alternately add and subtract the digits and then compute the remainder of that result.

  Why it works: we write numbers in base $10$, and $10 \equiv -1$ mod $11$, so multiplying by $10$ is really multiplying by $-1$ (changing the sign).

You can read more about these divisibility rules and others at this Wikipedia page.

Answer 2

Hint:

$$1\bmod9=10\bmod9=100\bmod9=1000\bmod9=\cdots 1,$$ $$1\bmod11=100\bmod11=\cdots 1,$$ $$10\bmod11=1000\bmod11=\cdots-1.$$

See the decimal expansion as a linear combination.

Answer 3

Radix notation has $\color{#c00}P\!$$\textit{olynomial form}$ $\, n = \color{#c00}{P}(10) = d_k 10^k +\cdots + d_2\cdot 10^2 + d_1\cdot 10 + d_0\, $

so $\, {\rm mod}\ 9\!:\, \color{#0a0}{10\equiv 1}\,\Rightarrow\, P(\color{#0a0}{10})\,\equiv\, P(\color{#0a0}1)\,\equiv\, d_k+\cdots + d_1 + d_0 = $ sum of digits $\,d_i,\ $ and

$ {\rm mod}\ 11\!:\, \color{#90f}{10\equiv -1}\,\Rightarrow\, P(\color{#90f}{10})\equiv P(\color{#90f}{-1})\equiv (-1)^k d_k+\cdots - d_1 + d_0 = $ alternating digit sum.

In both cases we employed the the $ $ Polynomial Congruence Rule, $ $ i.e. $\,a\equiv b\,\Rightarrow\,P(a)\equiv P(b),\ $ for any polynomial $\,P(x)\,$ with integer coefficients, and any integers $\,a,b.$

---

Remark $\ $ These tests are special cases $\,(x = 10)\,$ of results true for any polynomial, namely

$ {\rm mod}\ x\!-\!1\!:\,\ \color{#0a0}{x\ \equiv\ 1}\ \Rightarrow\ P(\color{#0a0}{x})\,\equiv\, P(\color{#0a0}1)\,\equiv\, d_k+\cdots + d_1 + d_0 = $ sum of coef's $\,d_i,\ $ and

$ {\rm mod}\ x\!+\!1\!:\,\ \color{#90f}{x\equiv -1}\,\Rightarrow\, P(\color{#90f}{x})\equiv P(\color{#90f}{-1})\equiv (-1)^k d_k+\cdots - d_1 + d_0 = $ alternating coef sum.

Thus if the coef sum $\,P(1) = 0\,$ then $\,P(x)\equiv P(1)\equiv 0\,\pmod{x\!-\!1}\,\ $ so $\,\ x\!-\!1\mid P(x),$

and, similarly, if $\ P(-1) = 0\,$ then $\,P(x)\equiv P(-1)\equiv 0\pmod{x\!+\!1}\,\ $ so $\,\ x\!+\!1\mid P(x).$

Both are special case of the well-known $ $ Factor Theorem $\,\ x\!-\!a\,\mid\, P(x)-P(a).$

In particular, for $\,x = b = \,$ radix, we get the base $b$ analog of casting out $9$ and $11$ in radix $10$