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(4): solution by Kirk)

Sorry to not be able to explain "mod m" to your satisfaction. My correction needs a correction too -- that first:
(10^n)%11=((-1)^n))%m
should have been
(10^n)%11=((-1)^n))%11 ,
that is m=11 here and I should have just used 11 instead of m. Thus 1000 and -1 are congruent mod 11 since
1000%11=10, and -1%11=10 as -1=-1*11+10.
Notice that the remainder is always nonnegative and less than the modulus -- this is what remainder means.

As to a=m*(a/m)+a%m=q*m+r, the point is that here / indicates integer division as would be performed (at least for positive numbers) on integer variables in a computer program. a/m is an integer, not a fraction. It is the quotient when you divide a by m. You should have been able to discern this from the q*m +r.
As for the rest, the idea is simply that remaindering can be mixed in with adding, subtracting and multiplying (we will avoid dividing, so as not to get into something a little more complicated). The reason we would want to mix remaindering in with addition, subtraction and multiplication is to keep the number sizes small. Consider the problem of deciding what (10^24)%13 is. Instead of doing the whole long division of 1000000000000000000000000 by 13, we can, for example, do ((10000%13)^6)%13 and get the same answer: 10000%13=3, 3^6=729, 729%13=1, and hence
(10^24)%13=1. Since a decimal number n with digit string abcd equals a*10^3+b*10^2+c*10^1+d*10^0, n%13 is congruent mod 13 to n'=a*12+b*6+c*10+d because we can remainder the powers of 10 in advance. Then if we want n%13 we can calculate n'%13 instead and get the same answer. For the modulus 9, n%9=(a+b+c+d)%9, and for the modulus 11, n%11=(a*10+b+c*10+d)%11=(-a+b-c+d)%11.

You should be able to give a proof that
(a+b)%m=((a%m)+(b%m))%m.

In closing, here is a reliable maxim (in my opinion): "Mathematics is learned, not taught."

Posted by Richard on 2003-11-22 21:34:28