Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
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
add comment

4 Answers

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$.

share|improve this answer
add comment

$$\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)$$

share|improve this answer
add comment

$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)$

share|improve this answer
add comment

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).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.