# Prove general divisibility test by 11 by Induction.

Note: This is not a duplicate as I am asking for a proof, not a criteria, and this is a specific proof, not just any proof – please treat like any other question on a specific math problem. Please do not close. thanks!

I am having trouble proving the above as I don't know how to express the various cases/outcomes of N when 11 is added to M. Take for example N=9759, then M=9-7+5-9=0

However, M+11 could give many different numbers, depending on where and what integers are added.

So for M to become 0+11=11 in the above example,

(i) N=9757946 is one possibility

(ii) N=9469757 is another possibility

Although they are essentially the same, mathematically they are different (I think?) because:

(i) M=9-7+5-7+9-4+6

(ii) M=9-4+6 -9+7-5+7

so the (-1)^n coefficient changes for the digits 9, 7, 5, 7

These proofs for divisibility by 3 may help:

I'm a bit sceptical(*) to those proofs for the criterion for divisibily by $3$ so I wouldn't use them as a template for such a proof.

The trick is to compute the sum in modulo $11$ algebra. What we basically use is that $10^{2k}-1$ and $10^{2k+1}+1$ are divisible by $11$ or $10^k-(-1)^k$ are. We use this to compute the sum:

$$a = \sum a_k10^k = \sum a_k (10^k-(-1)^k+(-1)^k) = \sum (10^k-(-1)^k)a_k + \sum (-1)^ka_k$$

Where the first sum in the end is divisible by $11$ so therefore $a$ is divisible by $11$ iff the last sum is (which is that of the criterion).

That $10^k - (-1)^k$ is divisible by $11$ is shown by induction. If $k=1$ the expression equals $10^1 - (-1) = 11$. Now if $10^k - (-1)^k$ is divisible by $11$ then so is $10(10^{k} - (-1)^k) = 10^{k+1}-11(-1)^k - (-1)^{k+1}$, but since $11(-1)$ is divisible by $11$ then so is $10^{k+1}- (-1)^{k+1}$.

(*) Apart from that there is an obvious printing error in the objective (both being "Proving that if the sum of the digits is divisible by $3$, then the integer is divisibly by $3$") of the parts there's more problems. In the first part the proof of $P(1)$ is basically incorrect, if the sum of the integers is $3$ it's by no means guaranteed that the number it self is $3$, you could for example have that the number is $111$ which makes the sum $3$, but certainly $111\ne 3$. Similar objection can be made to the induction step.

The second part is a bit better, but when it comes to splitting up into two cases it's incomplete. They correctly handles the situation where you get carry, but it ignores the possibility of propagating carry that is $a_1+1>9$.

• Forgive my stupidity, but do you mean to use your answer, I should scrap my answer and only use induction for the 10^k-(-1)^k bit? Thanks. Commented Jul 17, 2017 at 9:34
• You have not shown your approach or solution so I can't tell if that's any good, but I use induction only to show that $10^k-(-1)^k$ is divisible by $11$ the rest is just a matter of rewriting sums (with rules which of course could be proven by induction too if you want to). I'm a bit sceptical to the proofs for the criterion for divisibility by $3$ so I wouldn't use them as a template for such a proof. Commented Jul 17, 2017 at 10:03
• My approach can be seen in the first image in my question^ Commented Jul 17, 2017 at 10:33
• I updated my answer explaining why trying to copy the proofs for the criterion for divisibility by $3$ is problematic, especially the first part (which is what you've tried) of the proof has some problems that needs to be addressed. Commented Jul 17, 2017 at 10:47
• @AnnaCHOI Because if you have for example $297$ having the sum $2+9+7 = 18$ and then by adding $3$ to $297$ the first case would mean to consider the sum $2+9+10$ and the second would mean the sum $2+10+0$. What we need to do is to handle the carry from the tens part and get the sum $3+0+0$ instead. Similarily we need to handle the situation where the hundreds and thousands results in carry and so on. Commented Jul 20, 2017 at 7:44

Hint  Assume for induction $\,{\rm mod}\ 11\!:\,\ \color{#c00}{f(10)\equiv f(-1)}\, [\,\equiv\rm alternating\ coef\ sum]\,$ for all polynomials $f(x)$ with integer coef's of degree $< n$. Then it also holds for a degree $n$ poly by

$\ \ f(x) = a + x\,\hat f(x)\$ so $\ f(10)\equiv a + \color{#0a0}{10}\, \color{#c00}{\hat f(10)}\equiv a +\color{#0a0}{(-1)} \color{#c00}{\hat f(-1)}\equiv f(-1)\,\pmod{\!11}$

where, by $\,\deg \hat f < \deg f,\,$ induction applies to $\,\color{#c00}{\hat f(10)}.\,$ We also used $\,\color{#0a0}{10\equiv -1}\pmod{\!11}$

Remark  This is a special case of the Polynomial Congruence Rule, an inductive extension of the Sum and Product Rules (which are both implicitly used above in the inductive step, to deduce that $b\equiv -1,\, c\equiv \hat c\,\Rightarrow a + bc\equiv a - \hat c).$

• I thought that f(10)≡ f(-1) already and we don't need to assume...? Commented Jul 20, 2017 at 7:25
• @AnnaCHOI If you already know that result (or the Polynomial Congruence Rule) then the result is immediate. Commented Jul 20, 2017 at 14:09

I came up with an alternative and I wonder if this is valid?