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.

I have seen the following one. Please give the proof of the observation. We know that, The difference between the sum of the odd numbered digits (1st, 3rd, 5th...) and the sum of the even numbered digits (2nd, 4th...) is divisible by 11. I have checked the same for other numbers in different base system. For example, if we want to know 27 is divisible by 3 or not. To check the divisibility for 3, take 1 lees than 3 (i.e., 2) and follow as shown bellow now 27 = 2 X 13 + 1 and then 13 = 2 X 6 + 1 and then 6 = 2 X 3 + 0 and then 3 = 2 X 1 + 1 and then 1 = 2 X 0 + 1 Now the remainders in base system is 27 = 11011 sum of altranative digits and their diffrence is ( 1 + 0 + 1) - (1 + 1) = 0 So, 27 is divisible by 3. What I want to say that, to check the divisibility of a number K, we will write the number in K-1 base system and then we apply the 11 divisibility rule. How this method is working.Please give me the proof. Thanks in advance.

share|improve this question
3  
That's a keen observation. You might want to look at modular arithmetic. Also, just as you generalized from $11$ to $b+1$ in base $b$, there are generalizations of the divisibility rules for $2$ and $5$ to the divisors of $b$ and of the divisibility rules for $3$ and $9$ to the divisors of $b-1$. –  joriki Jul 19 '11 at 10:20

2 Answers 2

Your question is rather confusingly written, but I assume you're asking for a proof that the base-10 divisibility rule for 11 — sum the even-numbered digits, subtract the odd-numbered digits, check (recursively) if result is divisible by 11 — can be generalized to a divisibility rule for $n+1$ in base $n$.

For a simple proof, let $x = \sum_{k=0}^\infty x_k n^k$, where $n$ is the base and $x_0$, $x_1$, $x_2$, etc. are the base-$n$ digits of $x$. Since $n \equiv -1 \mod n+1$, we have

$$ n^k \equiv (-1)^k = \begin{cases} \phantom{+}1 & \text{if }k\text{ is even,} \\ -1 & \text{if }k\text{ is odd,} \end{cases}\mod n+1 $$

and therefore

$$ x = \sum_{k=0}^\infty x_k n^k \equiv \sum_{k=0}^\infty x_k (-1)^k = \sum_{k\text{ even}} x_k - \sum_{k\text{ odd}} x_k \mod n+1.$$

Thus, $x$ is divisible by $n+1$ if and only if the sum of its even base-$n$ digits minus the sum of its odd base-$n$ digits is divisible by $n+1$.

share|improve this answer

Yes, the test for divisibility by $11$ generalizes to arbitrary radix. Using modular arithmetic this amounts to simply evaluating a polynomial. Notice that radix notation has polynomial form. Namely in radix $\rm\:b\:$ the digit string $\rm\ d_n\ \cdots\ d_1\ d_0\ $ denotes $\rm\ d_n\ b^n +\:\cdots\: + d_1\ b + d_0\: =\ P(b),\ $ where $\rm\:\ P(x)\: =\ d_n\ x^n +\:\cdots\: d_1\ x + d_0\ $ is the polynomial associated to the string of digits.

Therefore $\rm\ mod\ b+1\ $ we infer $\rm\ b\equiv -1\ $ $\Rightarrow$ $\rm\ P(b)\equiv P(-1)\equiv d_0 - d_1 + d_2 - d_3 +\:\cdots\:.\: $ Similar modular reductions yield analogous divisibility tests, e.g. see here for casting out $91$'s.

If modular arithmetic is unfamiliar then one may proceed more simply as follows:

Factor Theorem $\rm\;\Rightarrow\; x-a\ |\ P(x)-P(a)\ $ so $\rm\ x = b,\ a= -1\ \Rightarrow\ b+1\ |\ P(b)-P(-1)\:.$

See also this post and various other posts on generalizations of casting out nines.

share|improve this answer

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.