Can a Sequence of 1's and 0's Be a Multiple of Any Integer?

[Kummer]

Show that for any n>1 we can construct a positive integer consisting of only 1's and 0's such that this integer is a multiple of n.

 

[matt grime]

Interesting variation: show that if n is no divisbible by 2 or 5, then there you can choose this multiple to have precisely two 1s and the rest of the digits 0.

 

[NateTG]

Interesting variation: show that if n is no divisbible by 2 or 5, then there you can choose this multiple to have precisely two 1s and the rest of the digits 0.

Can you show example answers for, say, n=3 or n=9?

I do wonder how interesting a 'minimal' condition would make this though.

 

[Kummer]

A Big Hint

Given (n+1) integers show that there exists two whose difference is a divisible by n.

 

[NateTG]

The problem is fairily easy...

$$k=\sum_{i=1}^{n} 10^{i\phi(n)}$$
where $\phi(n)$ is the Euler Totient function.

Is divisible by $n$.

Alternatively, if we take $n^2-n+1$ integers then at least $n$ of them must have the same residue mod $n$, so their sum is equal to zero mod $n$, so if we take the first $n^2-n+1$ powers of 10, some sum will be equal to zero mod n, and that sum will clearly be zeros and ones.

 

[matt grime]

My special case was: if 10 and n are coprime, let r be the order of 10 in the units mod n, then 10^r-1 is divisble by n.

 

[NateTG]

My special case was: if 10 and n are coprime, let r be the order of 10 in the units mod n, then 10^r-1 is divisble by n.

But that's all 9's. Of course, this leads to a marginally more challenging version:

Show that every number has a (non-trivial) multiple which is some number of ones, followed by some number of zeros.

 

[matt grime]

Duh. Some times I even surprise myself with my idiocy - we need -1 =some power of n. So if n=p is prime, then we need that 10 has even order mod p - for then 1 has two square roots, 1 and -1

 

[Kummer]

My version is the easiest if you used my hint.

Theorem: If there are (n+1) distinct integers then there exists two who 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 we can find 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 when subtracted are divisible by n. But when we subtract them we end up with a number consisting of only 1's and 0's. In fact, the 1's and 0's are groupped together which answers the more difficult question stated by NateTG

 

[NateTG]

Kummer: How about showing that any number not divisible by 2 or 5 has a multiple that is all 1s?

 

[matt grime]

Kummer, I think you're under the mistake apprehension that we found your question hard...

 

[Kummer]

Kummer, I think you're under the mistake apprehension that we found your question hard...

The question is not hard. It is fun and I wanted to show it to you.

 

[matt grime]

Here's another (but very similar) way of showing it:

consider the sequence 10^m mod n. This is periodic, by the pigeon hole principle. There for there are s,r integers with 10^s=10^{s+kr} mod n for k natural numbers k. Just add up any n different such powers of 10.

 

[NateTG]

Hmm, I wonder if there's some way to find the minimum such multiple, or the average minimum multiple.

 

[matt grime]

I should have been more pedantic: the sequence is eventually periodic. It need not be periodic. The idea being that at some point you must have a repeated residue, and then it becomes periodic - if 10 were invertible, then you could guarantee to run it backwards too. Eg. say n=100, the sequence goes 10,0,0,0,0,0,...