In case you are wondering about the part of the proof for k%3<>0, it goes like this, the given number can be written as 1 + 1000 + 1000000 + 1000000000 +..and so on now if for a given k, if we choose the string of k 1s and try to find the modulus with each of the terms in the above expression, for all the terms less that 1111...1 (k times) will be the numbers themselves, for the rest of the terms, this will give 1(000)*00 and 1(000)*0 as the remainders.
Consider any number as 1 followed by m zeros, the remainder when divided by k1s would be 1 followed by (m%k) zeroes. Now, there is a beautiful property, consider the sequence 0,3,6,9,12,15,18.... (all the multiples of 3) and try to take mod k (assuming k%3 <>0 and therefore k is only going to intersect at the point 3k). The series is 0,3,6...k-(k%3), k+(k%3), ...., 2k-(2k%3), 2k+(2k%3)...3k This is valid since k%3 and 2k%3 are going to be non zero since k % 3<>0. Now note that when taking mod k, the sequence of remainders after k - (k%3) will be offset by either 1 or 2 . If it is offset by 1 then after 2k%3 it will be offset by 2, If by 2 after k-(k%3) then by 1 after 2k%3. Therefore the sequence 0,3,6,9...2k under modulus k (k%3<>0) produces all the numbers from 0..k-1. This completes the proof, since the set of numbers with 1 followed by 0 to k-1 zeroes when added will give 111..1 k times. Therefore the number 1 + 1000 + 1000000 + 1000000000 +.. (till 1 (3k)* ) will be divisible by 111..1 ( k times). --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
