Complete proof of divisibility rule for 9 in n digits

professionalbronco

Suppose we have a $n$ digit number $\overline{a_na_{n-1}\cdots a_2a_1a_0}$ where the $a_i$'s are digits. Writing this as powers of $10$, we get

$$\overline{a_na_{n-1}\cdots a_2a_1}=a_n\cdot 10^n+a_{n-1}\cdot 10^{n-1}+\cdots+a_2\cdot 10^2+a_1\cdot 10+a_0\pmod{9}. $$

Notice that $10\equiv 1\pmod{9}$, which means that $10^n\equiv 1^n\equiv 1\pmod{9}$. So, we can rewrite the previous expression as

$$a_n\cdot 1+a_{n-1}\cdot 1+a_{n-2}\cdot 1+\cdots+a_2\cdot 1+a_1\cdot 1+a_0\cdot 1\equiv a_n+a_{n-1}+a_{n-2}+\cdots+a_2+a_1+a_0\pmod{9}. $$

This is the same as the sum of the digits mod 9. Hence, we have found and proved the divisibility rule for 9.

I hope this was helpful!

Note: the same divisibility rule also works for 3 because $10\equiv 1\pmod{3}$.
Mods: can you check this proof?

quacker88

@professionalbronco Way to go!! That's exactly right, and good job for making everything so clear and concise!

Using this, I have two challenges for you:

The divisibility rule for 11 is that if you alternate adding and subtracting the digits of a number and the result is divisible by 11, then the original number is divisible by 11. For example, take 18953: 1-8+9-5+3=0, which is divisible by 11, so 18593 is divisible by 11. Can you prove this?
Even harder: the divisibility rule for 7 is that you take the last digit, double it, and subtract it from the rest of the number. If the resulting number is divisible by 7, then the original number is divisible by 7 also. For example, 1001 --> last digit is 1, doubling it gives you 2 --> 100-2 = 98 which is divisible by 7, so 1001 is divisible by 7.
This one is pretty tough, so if you need a hint: $\color{white} \text{note that } 5 \cdot 10 \equiv 1 \pmod{7}! $
To view the hint, just highlight the stuff after "hint". It's in white text, so you can't see it without highlighting it. I'm not sure if you'll need it, so it's there if you want Good luck!

professionalbronco

@quacker88 Actually there is a mistake in my proof. I will edit it later.

Question #1 isn't very hard.
S1: Suppose we have a number $\overline{a_na_{n-1}\cdots a_2a_1a_0}$ where the $a_i$'s are digits. Writing this as a sum of powers of $10$, we get

$$\overline{a_na_{n-1}\cdots a_2a_1}=a_n\cdot 10^n+a_{n-1}\cdot 10^{n-1}+\cdots+a_2\cdot 10^2+a_1\cdot 10+a_0. $$

Notice that $11\equiv -1\pmod{10}$; this means that $11^n\equiv (-1)^n\pmod{10}$. So, we can rewrite the expression mod 9 as

$$a_n\cdot 10^n+a_{n-1}\cdot 10^{n-1}+\cdots+a_2\cdot 10^2+a_1\cdot 10+a_0\equiv a_n\cdot (-1)^n+a_{n-1}\cdot (-1)^{n-1}+\cdots+a_2\cdot (-1)^2+a_1\cdot (-1)+a_0\pmod{11} $$

This is the alternating sum of digits, hence, we have proved the divisibility rule for 11.

Note 1. The number $\overline{a_na_{n-1}\cdots a_2a_1a_0}$ has $\boldsymbol{n+1}$ digits, not $n$ digits.
Note 2.
If $n$ is odd, then we will have the sum $-a_n+a_{n-1}-a_{n-2}+\cdots+a_2-a_1+a_0$. This means we have to first negate the first digit and then do the alternating sum to find the remainder mod 11.
If $n$ is even, then the sum is $a_n-a_{n-1}+a_{n-2}-\cdots+a_2-a_1+a_0$. This means we leave the first digit as is and then do the alternating sum to find the remainder mod 11.

I will post my solution to Question #2 later.