# How to prove this property of congruences?

Prove that for each $n \in \mathbb{N}, s \in \mathbb{N}$ the following is true

(i) $n \equiv Q_s(n) \left(\bmod\ 10^s - 1\right)$

(ii) $n \equiv Q'_s(n)\left(\bmod\ 10^s + 1\right)$

where

$$Q_s(n) = \sum_{i=0}^{\infty}(a_{is+s-1}\dots a_{is+1}a_{is})$$

for example

$$Q_3 (6154328103) = 103 + 328 + 154 + 006 = 591$$

and

$$Q'_s(n) = \sum_{i=0}^{\infty}(-1^i)(a_{is+s-1}\dots a_{is+1}a_{is})$$

for example

$$Q'_3 (6154328103) = 103 - 328 + 154 - 006 = -77$$

Also $n$ can be expressed as

$$n = \sum_{i=0}^{\infty}(a_{is+s-1}\dots a_{is+1}a_{is}) \cdot 10^{is}$$

for example

$$6154328103 = 103 \cdot 10^{0 \cdot 3} + 328 \cdot 10^{1 \cdot 3} + 154 \cdot 10^{2 \cdot 3} + 6 \cdot 10^{3 \cdot 3}$$

Any ideas?

-
Do you recognize these as generalizations of the usual tests for divisibility by $9$ and by $11$? I expect you have seen the proofs of correctness for those. – André Nicolas Feb 28 '12 at 22:21
A biologist, eh? Anyways, you should at least explain that the $a_k$'s stand for the digits in base expansions of the argument. – anon Feb 28 '12 at 22:22

Hint: mod $10^s -1$ we have $10^s\equiv 1$, and mod $10^s + 1$ we have $10^s\equiv -1$. Use these congruences as rewrite rules to replace powers of $10^s$ by powers of $\pm 1$ in radix $10^s$ representation.

This leads to simple universal divisibility tests: evaluate a radix polynomial in nested Horner form, using modular arithmetic. For example, consider evaluating a $3$ digit radix $10$ number modulo $7$. In Horner form $\rm\ d_2\: d_1\:d_0 \$ is $\rm\: (d_2\cdot 10 + d_1)\ 10 + d_0\ \equiv\ (d_2\cdot 3 + d_1)\ 3 + d_0\ (mod\ 7)\$ since $\rm\ 10\equiv 3\ (mod\ 7)\:.\:$ So we compute the remainder $\rm\ (mod\ 7)\$ as follows. Start with the leading digit then repeatedly apply the operation: multiply by $3$ then add the next digit, doing all of the arithmetic $\rm\:(mod\ 7)\:.\:$

For example, let's use this algorithm to reduce $\rm\ 43211\ \:(mod\ 7)\:.\:$ The algorithm consists of repeatedly replacing the first two leading digits $\rm\ d_n\: d_{n-1}\$ by $\rm\ d_n\cdot 3 + d_{n-1}\:\ (mod\ 7),\:$ namely

$\rm\qquad\phantom{\equiv} \color{red}{4\ 3}\ 2\ 1\ 1$

$\rm\qquad\equiv\phantom{4} \color{green}{1\ 2}\ 1\ 1\quad$ by $\rm\quad \color{red}4\cdot 3 + \color{red}3\ \equiv\ \color{green}1$

$\rm\qquad\equiv\phantom{4\ 3} \color{royalblue}{5\ 1}\ 1\quad$ by $\rm\quad \color{green}1\cdot 3 + \color{green}2\ \equiv\ \color{royalblue}5$

$\rm\qquad\equiv\phantom{4\ 3\ 5} \color{brown}{2\ 1}\quad$ by $\rm\quad \color{royalblue}5\cdot 3 + \color{royalblue}1\ \equiv\ \color{brown}2$

$\rm\qquad\equiv\phantom{4\ 3\ 5\ 2} 0\quad$ by $\rm\quad \color{brown}2\cdot 3 + \color{brown}1\ \equiv\ 0$

Hence $\rm\ 43211\equiv 0\:\ (mod\ 7)\:,\:$ indeed $\rm\ 43211 = 7\cdot 6173\:.\:$ Notice that for modulus $11$ or $9\:$ the above method reduces to the well-known divisibility tests by $11$ or $9\:$ (a.k.a. "casting out nines" for modulus $9$). Your examples are analogous: casting out $11\cdots1$ or $99\cdots9$.

-

$$\rm b\equiv 1 \implies a_k b^k+ a_{k-1} b^{k-1}+\cdots +a_1b+a_0\equiv a_k+a_{k-1}+\cdots+a_1+a_0 \bmod (b-1)$$

$$\rm b\equiv -1 \implies \large\circ \normalsize =a_k(-1)^k+a_{k-1}(-1)^{k-1}+\cdots-a_1+a_0 \bmod (b+1)$$

-

For $i \ge 0$, denote $n_i = (a_{is+s-1} \cdots a_{is})$, and $b = 10^s$. From $b \equiv 1 \mod (b - 1)$, we get

$$n = \sum_{i = 0}^{\infty} n_i b^i \equiv \sum_{i = 0}^{\infty} n_i = Q_s(n) \mod (b-1)$$

Similarly, from $b \equiv -1 \mod (b+1)$, we get

$$n = \sum_{i = 0}^{\infty} n_i b^i \equiv \sum_{i = 0}^{\infty} n_i (-1)^i = Q_s'(n) \mod (b+1)$$

Note that for $s = 1$, you get the well known divibility criterion by $9$ (namely that a number is divisible by $9$ if and only if the sum of its digit is).

-

$6154328103=6,000,000,000+154,000,000+328,000+103=(6)(1,000,000,000)+(154)(1,000,000)+(328)(1,000)+103=(6)(999,999,999+1)+(154)(999,999+1)+(328)(999+1)+103=6+154+328+103+(999)x$ where $x=(6)(1,001,001)+(154)(1,001)+(328)(1)$

-