Answer to Question #326604 in Combinatorics | Number Theory for Allen

Question

Prove:

The following methods are useful for divisibility by 11.

1. Get the difference of the sum of the digits in the odd places and the sum

of the digits in the even places. If the result is divisible by 11, then 11|N.

Answer 1

Let's use some facts ('a mod z' means remainder of division of a by z):

$1)\space10\space mod\space 11=-1\\ 2)\space100\space mod\space 11=1$

Replacing terms with their remainders of division will not affect on the resulting remainder:

$3)\space(a+b)_\space mod\space z=(a\space mod\space z+b)\space mod\space z\\ =(a\space mod\space z+b\space mod\space z)\space mod\space z\\ 4)\space(ab)\space mod\space z=(a\space mod\space z\cdot b)\space mod\space z=\\ =(a\space mod\space z\cdot b\space mod\space z)\space mod\space z\\ 5)\space(x^p)\space mod\space z=(x\space mod\space z)^p\space mod\space z$

Let $a_i$ be digits of number n

n is divisible by 11 if and only if n mod 11 = 0

$n\space mod\space 11=\\ (a_0+10a_1+10^2a_2+...+10^ka_k)\space mod\space 11=\\ =(a_0+10^2a_2+...+10^{2p}a_{2p}+\\ +10a_1+10^3a_3+...+10^{2q+1}a_{2q+1})\space mod\space 11=\\ (a_0+...+(100\space mod\space 11)^pa_{2p}+\\ (10\space mod\space 11)a_1+...\\ +(10\space mod\space 11)^{2q+1}a_{2q+1})\space mod\space 11=\\ (a_0+...+a_{2p}-a_1-...-a_{2q+1})\space mod\space 11\\ n\space mod\space 11=0\Lrarr\\ \Lrarr(a_0+...+a_{2p}-(a_1+...+a_{2q+1}))\space mod\space 11=0$