### alpenglow's blog

By alpenglow, history, 4 weeks ago, Recently I was solving the problem which said that I have to find the smallest number consisting of only 1-s (1, 11, 111, ...) which will be divisible by the given number $n$. This problem is easy, but I was surprised that it is possible for any $n$ not divisible $2$ and $5$. (at least for $<= 100 000$). How can I prove this? Comments (7)
 » I hate to be that guy, but technically it isn't possible for any $n$. $n=10$, $n=5$, and $n=2$ are all break cases.
•  » » Forgot to mention, any numbers except those divisible by $2$ and $5$.Thanks.
 » 4 weeks ago, # | ← Rev. 2 →   write down all numbers 1,11,111,...,11...1 (n+1 times). now you have $n+1$ numbers,but at most $n$ different values modulo $n$,so pigeonhole says two of them have same remainder modulo $n$. take these two,subtract smaller one from larger one,and you will have some number like 11...100...0that is divisible by $n$.now you can remove all trailing zeros(because it doesn't change divisibility by $n$) and you will have some 11...1 divisible by $n$.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   because it doesn't change divisibility by nBut why? It's not obvious at all. When you remove the trailing zeros the number will become the sum of different powers of 10. For example 110 is divisible by 5 but 11 is not although 5 is not included in here. It's not easy to believe that.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   $a \mid 10^kb, gcd(10^k, a) = 1 \Rightarrow a \mid b$.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   consider you have $d = 11...100...0$ . - $d$ is divisible by $n$ ,so $d = nk$ for some $k$. - $d$ is divisible by 10 ,but $gcd(n,10) = 1$.so $d = n*q*10^p$ for some $q$ and $p$. so when you divide $d$ by $10^p$, $d$ becomes equal to $nq$. so $d$ remains divisible by $n$.UPD : fixed a minor bug!
 » 4 weeks ago, # | ← Rev. 2 →   Hello there, I went searching for the answer, ended up with this interesting blog , I think it might help you.Summary of the proof is: the all-1-sequence is infinte, so as you mod each all-1 number by n, (where n is not a multiple of 2 or 5, means n%10 != 0)Either one of the remainders is 0, so boom! Divided.Or, the sequence being infinite, at one point a number shall occur a second time in the remainders list. (From pigeonhole principle, even in worst case, within every (n+1)th iteration, as we mod by n)Now if for 2 all-1 numbers a and b, a % n == b % n then => (a-b) % n == 0again, as a and b are all-1 numbers and if a > b,the number a-b will be of the form 111...10...000 (p x 10^q, where p is an all-1 number and q is a positive integer)But as we assumed n%10!=0, n (and eventually any multiple of n) cannot have trailing zeroes, That means, 10^q % n != 0But (p x 10^q) % n == 0So, from modular arithmetic, p % n == 0 and we already agreed that p itself is an all-1 number.