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?

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.

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...0`

that 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$$$.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.

$$$a \mid 10^kb, gcd(10^k, a) = 1 \Rightarrow a \mid b$$$.

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!

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 nota 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 asecond timein the remainders list. (Frompigeonhole 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 == 0`

again, as a and b are all-1 numbers and if a > b,

the number

a-bwill 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)cannothavetrailing zeroes,That means,

`10^q % n != 0`

But

`(p x 10^q) % n == 0`

So, from modular arithmetic,

`p % n == 0`

and we already agreed that p itself is an all-1 number.