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.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s