# Generalised Divisibility

I have a following question:

Can we find for any natural number $$n \in \mathbb{N}$$, a sequence of only $$\{0,1\}$$ as elements such that the sequence has exactly $$n\ 1's$$ and is divisible by $$n$$ when viewed as a natural number. I can form easily a number with exactly $$n$$ ones but then how do I check that this sequence is divisible by $$n$$. Maybe the problem requires some combinatorial argument which I cant see properly.$$\\$$

For example, $$3 \in \mathbb{N}$$ corresponds to $$111$$ and $$101010$$ in the set of sequences. Both these are elements such that they have $$3$$ ones and $$3$$ divides them. If $$n=4$$, then we have the sequences $$111100$$ and $$1101100$$ etc. such that there are $$4$$ ones and $$4$$ divides them. Also, if $$n=5$$, we have $$111110$$, $$10101110$$ etc, which are divisible by $$5$$ and have $$5$$ ones. The point is that there can be more than one sequences which satisfy the given properties but how to show that one exists when the numbers are larger say $$n=143$$ etc. $$\\$$

Any hint/help would be nice. Thanks

• I don't understand your description of your goal. Please edit the question to show us examples of sequences that work and that don't work for the numbers from $1$ to $10$. Then maybe we can help. – Ethan Bolker Apr 17 at 10:03
• Not clear. Are you allowing infinite sequences of $1's$ and $0's$? All your examples are finite. If you restrict to finite one, then the list of such is countable. – lulu Apr 17 at 10:37
• Oh yes they are countable sequences. – Rick Apr 17 at 10:39
• Not following. You said "it is an uncountable set". Well, what is "it"? I assumed you meant the set of sequences of $0's, 1's$. But if that is only true if you allow infinite sequences of $0's, 1's$. Please clarify. – lulu Apr 17 at 10:47
• ok, now I get that I made a mistake, thanks for pointing that out. Moreover, I was more concerned with the divisibility part/ how to show the existence of a number which is divisible by $n \in \mathbb{N}$. – Rick Apr 17 at 11:16

Suppose $$\gcd(n,10)=1$$. Then there is some $$P>0$$ such that $$10^P\equiv 1 \pmod n$$. It follows that $$10^0, 10^P, \cdots, 10^{(n-1)P}$$ are all $$\equiv 1 \pmod n$$. But then $$\sum_{i=0}^{n-1} 10^{iP}\equiv 0\pmod n$$ so you have an example of the sort of sequence you want.
Of course, if $$\gcd(n,10)>1$$ we can write $$n=2^a5^bN$$ with $$\gcd(N,10)=1$$. Then perform the above construction using $$n$$ $$1's$$ to get a sequence divisible by $$N$$. After that multiply by $$10^{\max(a,b)}$$ to finish.
Note: this construction isn't exactly efficient, meaning that there is no suggestion that it finds a minimal example. If $$n=7$$, say, $$P=6$$ so the construction leads us to $$1+10^6+10^{12}+10^{18}+10^{24}+10^{30}+10^{36}$$, or $$1000001000001000001000001000001000001$$ while, of course, $$11101111$$ works as well.