# Congruence Summation Notation

I am given this problem:

Suppose that a positive integer $n$, written in decimal notation, has digits (from left to right) $a_k, a_{k-1}, \ldots, a_0$. So $n = a_k 10^k + a_{k-1} 10^{k-1} + \cdots + a_1 10^1 + a_0$. Prove that $$n \equiv \sum_{i=0}^k (-1)^i a_i \equiv (-1)^k a_k + \cdots - a_3 + a_2 - a_1 + a_0 \quad \text{(mod 11)}$$

Now apply this result: let $b_n$ denote the number consisting, in decimal notation, of $n$ $1$'s. That is $$b_n = \underbrace{11 \cdots 1}_n$$ For which $n$ is $b_n$ divisible by $11$?

I am not sure how to approach this, what is the best way to solve this?

-
Are there other ways to solve this problem? I'm truly stuck. –  Dominick Gerard Mar 30 '12 at 14:04
add comment

## 1 Answer

$10 = -1 \mod 11$ and so $10^i = (-1)^i \mod 11$

Thus $$\sum_{i=0}^{k} a_i 10^i = \sum_{i=0}^{k} a_i (-1)^i \mod 11$$

Try computing the same for $b_n$ for some $n$. Do you see a pattern?

-
Sorry, I'm not sure, can you elaborate? –  Dominick Gerard Mar 30 '12 at 4:43
@DominickGerard: What are you not sure about? –  Aryabhata Mar 30 '12 at 4:46
i'm not sure that I see the pattern, kind of confused about how to find $b_n$ –  Dominick Gerard Mar 30 '12 at 12:51
@DominickGerard: $b_n$ is the n digit number where all digits are ones. The above rule says that if you take the sum of the digits which appear at even positions and take the sum of digits at odd position and subtract, the difference should be be divisible by 11 for the original number to be divisible by 11. For an eg of the application of the rule: 121. You take 1 + 1 -2 = 0. Which is divisble by 11. So 121 is also divisible by 11 If you consider 1234, (1+3) - (2+4) = -2, is not divisible by 11. So 1234 is not divisible by 11 . Now try it with $b_n$. –  Aryabhata Mar 30 '12 at 14:43
my best guess is that the $b_n$ with an even amount of digits are divisible by 11, but an odd amount are not (ie 1111 is divisble by 11, but 11111 is not). Is there a reason for this? or an eloquent way to put this? –  Dominick Gerard Mar 30 '12 at 15:03
show 6 more comments