All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 50 - Digit Number (Posted on 2003-11-15)
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.

 See The Solution Submitted by Ravi Raja Rating: 3.3333 (6 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 re(5): solution | Comment 25 of 39 |
(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

 Search: Search body:
Forums (0)