A number of 50 digits has all its digits equal to 1 except the 26th digit. If the number is divisible by 13, then find the digit in the 26th place.

(In reply to re(2): solution by Kirk)

Sorry, Kirk. I did not mean to intimidate you. Modular arithmetic should be pre-university, but maybe it isn't. It wasn't back in 1959 when I first went to college, but those were primitive times! Anyway, the idea is simply that given a fixed whole number m greater than 1 (called the modulus) we can do an interesting brand of arithmetic by only considering the remainders after dividing by m. When we do this, we say we are calculating modulo m, or for short, mod m. Two numbers are "the same" mod m (or "congruent" modulo m) if they leave the same remainder when divided by m. If we introduce the operator % (as in the C programming language) used to indicate remaindering, so that a%m means the remainder when a is divided by m, and use / to denote the quotient operation (or "integer divide") we have a=m*(a/m) + a%m=m*q+r. It is quite easy to show that (a+b)%m= (a%m+b%m)%m and (ab)%m= ((a%m)*(b%m))%m, which means we can remainder first before adding or multiplying without affecting the remainder of the result. It is this that makes casting out nines work as a checksum. Since (10^n)%9=1, 176923%9 =(1+7+6+9+2+3)%9=1. The same idea can be applied to digit problems using any value for m, although m=9 is the nicest for decimals, and m=11 is second nicest (since (10^n)%11=(-1)^n).

Working mod m is very basic in puzzle math. For example, working mod 7, it can be shown with a bit of work that every year must have at least one Friday the 13th (leap years must be treated separately).

I hope this clears up the concept of "mod m" for you and enables you to begin to use it in solving problems.

~Richard

Posted by Richard on 2003-11-21 17:48:09