This is very beautiful. Here is a less elegant proof, though it leads to an efficient algorithm.
In a different problem some time ago, there was a statement that every number with a 3 in the units position has a multiple that consists of all 1s. The proof needs a little number theory. Any number Z that is all 1's can be written as (10^e - 1) / 9 for some integer e. So if Y is the number we are given (ending in 3), we must find e such that (10^e - 1) / 9 == 0 (mod Y). From this, algebra provides 10^e - 1 == 0 (mod Y) and 10^e == 1 (mod Y). Note 10^e and Y are coprime. The prime factors of the former are all 5 and 2, and since Y ends in 3, it can have neither of these. Then by Euler's Theorem, e must exist (and in fact Euler's Totient Function gives its value)! So we are done. Corollary: a number with 1, 7, or, 9 in the units position also has a multiple that's all 1s. Proof: Multiply by 3, 9, or 7 respectively to get a number with 3 in the units position, then use the result above. The rest: Let X be the (arbitrary) number we are given. Divide out all its factors of 2 and 5 to obtain Y. Claim: Y has 1, 3, 7, or 9 in the units position. Proof: If it ended with any other digit, it would be divisible by 2 or 5! Therefore we can find a number Z consisting of all 1's that is a multiple of Y. Suppose we factored out (2^a)(5^b) above. Then Z (10^max(a, b)) is a number consisting of all 1's and 0's that is a multiple of X as desired! It's not hard to implement in this in time linear to the number of digits of the multiple (assuming a real RAM model of computation). Please let me know if you see any problems with this argument. On Mar 7, 4:32 pm, Don <dondod...@gmail.com> wrote: > Theorem: In any set of (n+1) distinct integers there exists two whose > difference is divisible by n. > > Proof: Each of these integers leaves a remainder between 0 and n-1 > inclusive upon division by n. Since there are n possible remainders > and (n+1) integers that means there exist two which have the same > remainder by the PigeonHole Principle. So their difference is > divisible by n. > > Theorem: Given any positive integer n there exists a positive number > consisting of only 1's and 0's which is divisible by n. > > Proof: Construct the sequence of (n+1) integers: > 1,11,111,....,111...1 > By the first theorem two of these numbers have a difference divisible > by n. That difference will be a number consisting of only 1's and > 0's. > > On Mar 7, 1:17 pm, karthikeya s <karthikeya.a...@gmail.com> wrote: > > > > > > > > > A math problem: Prove that for all positive integer n, there exist at least > > one positive integer whose digits are only 1s and 0s and is divisible by n. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
