Does the given prime number divide given number based on the given statement

Question

We will represent integer m by m = ($a_k$$a_{k-1}$...$a_0$)$_{10}$ = $a_k * 10 ^k + a_{k-1} * 10^{k-1} + ... + a_1*10 + a_0$ where 0 $\le$ $a_j$ $\le$ 9. Let p= 7 or 11 or 13. Show that p|m $\longleftrightarrow$ p|$($a$_2$a$_1$a$_0$)$_{10}$ - $($a$_5$a$_4$a$_3$)$_{10}$ + $($a$_8$a$_7$a$_6$)$_{10}$ - ... For example, to check if 13| 75787192, check if 13 divides 192 - 787 + 75. I have no clue how to start and show why exactly the above bi-implication holds.

Answer 1

This comes from the fact that $7,11,13\mid 1001$. To take your example, we have: $$ 75\,787\,192=75\,595\,000 +192\,192\\ =75\,595\,000+192\cdot 1001 $$ So, the first number is divisible by $13$ iff $75\,595\,000$ is divisible by $13$. Which is the same as $75\,595$ being divisible by $13$. Note that $595=787-192$.

Now do the same to $75\,595$, and you get $75\,595=520+75\cdot 1001$, meaning that $13$ divides $75\,595$ iff it divides $520=-192+787-75$. We have a minus sign here compared to your formula, but that doesn't affect anything.

This generalises almost without any issues to any numerator, and works equally well for $7,11$ and $13$, or any other divisor of $1001$.

There is some hassle if $a_2a_1a_0$ is larger than $a_5a_4a_3$. In the last step of the example above we were saved because it was the last step. If, however, the number had been $3\,075\,595$, we would've had to keep track of a borrow or a carry if we wanted to add or subtract multiples of $1001$ until the number ends in $000$. This doesn't change the result, but is a bit of extra work if you want to show the general theorem.