Problem of the week, 161

A former colleague Bill Wardlaw (March 3, 1936-January 2, 2013) used to create a “Problem of the Week” for his US Naval Academy students, giving a prize of a cookie if they could solve it. One of them is given below.

The residue of an integer n modulo an integer d > 1 is the remainder r left when n is divided by d. That is, if n = dq + r for integers q and r with 0 < r < d, we write $r \equiv n \pmod d$ for the residue of n modulo d. Show that the residue modulo 7 of a (large) integer n can be found by separating the integer into 3-digit blocks $n = b(s)b(s-1)\dots b(1)$ .(Note that b(s) may have 1, 2, or 3 digits, but every other block must have exactly three digits.) Then the residue modulo 7 of n is the same as the residue modulo 7 of $b(1) - b(2) + b(3) - b(4) + \dots \pm b(s)$ . For example,
$n = 25,379,885,124,961,154,398,521,655 \pmod 7$
$\equiv 655 - 521 + 398 - 154 + 961 - 124 + 885 - 379 + 25 \pmod 7$ $\equiv 1746 \pmod 7$ $\equiv 746 - 1 \pmod 7$ $\equiv 745 \pmod 7 \equiv 3 \pmod 7$ .
Explain why this works and show that the same trick works for residues modulo 13.