Divisibility by 7 of a number consisting of 0 and 1's

Question

A decimal number is of arbitrary length consisting of 0 and 1 only i.e. (10,111,10000,11111,1010, number of digits in the number can be upto 100 ) Can this number ever be divisible by 7 if yes, is there any efficient way to list all those numbers

Answer 1

You can consider 1,11,111,1111,11111,111111,1111111,11111111. You have 8 distinct numbers, so at least two of them are congruent mod 7 (pigeon hole principle). Their difference will be a number with 1s and 0s divisible by 7.

Answer 2

Note that $10 \equiv 3 \bmod 7$ and the powers of $3$ modulo $7$ are: $$3^0=1,\ 3^1=3,\ 3^2=2,\ 3^3=6,\ 3^4=4,\ 3^5=5$$ It follows that $10^k \equiv 3^r \bmod 7$ where $r$ is the remainder of $k$ modulo $6$, so you can find the remainder of a number consisting of only $0$s and $1$s modulo $7$ by splitting its decimal expansion into groups of $6$, replacing each '$1$' by whichever digit it corresponds to in the above, and adding them all together.

For example consider the number $110010 101010 010011$. We can break it up as $$110010~101010~010011$$ Using the above, this is congruent to $$(3^5+3^4+3^1)+(3^5+3^3+3^1)+(3^4+3^1+3^0)$$ which is itself congruent to $$(5+4+3)+(5+6+3)+(4+2+1)$$ modulo $7$. This gives $110010101010010011 \equiv 33 \equiv 6 \bmod 7$.

This gives an algorithm for determining whether such a number $n$ is divisible by $7$ (and its efficiency is $O(\log n)$, which is pretty good). This also hints at a way of listing all such numbers.

Answer 3

$10 \equiv 3 \pmod 7$ and so $10^2 \equiv 2\pmod 7$ and $10^3 \equiv -1\pmod 7$ and $10^4 \equiv -3 \pmod 7$ and $10^5 \equiv -2 \pmod 7$ and $10^6 \equiv 1 \pmod 7$.

Let $N = 10^{a_n} + 10^{a_{n-1}} + ....... + 10^{a_0}$ where no $a_i = a_j$ if $i\ne j$ be a number consisting of only $0$s and $1$.

Then $N \equiv b_n + b_{n-1} + ...... + b_0 \pmod 7$ where

where $b_k = \begin{cases} 1 &\text{if }a_k\equiv 0 \pmod 6\\ 3 &\text{if }a_k\equiv 1 \pmod 6\\ 2 &\text{if }a_k\equiv 2 \pmod 6\\ -1 &\text{if }a_k\equiv 3 \pmod 6\\ -3 &\text{if }a_k\equiv 4 \pmod 6\\ -2 &\text{if }a_k\equiv 5 \pmod 6\\ \end{cases}$

So Choose a bunch of $a_k$ where the sum of the $b_k$ add to $0$ or a multiple of $7$.

Example If $a_0 =0$ then $b_0=1$ and so if $a_1=3$ then $b_1=-1$ and so $10^{a_1} + 10^{a_0} =10^3+ 10^0 = 1001$ will have be divisible by $7$. And indeed $1001 = 7*143$.

Another example if $a_0=1$ and $a_1=2$ then $b_0=3$ and $b_1=2$ so $b_0 + b_1=5$ so we need the rest to and to $-5$ or $2$ or $2$ more than multiple of $7$.

So we could do $a_2=4$ and $a_3=5$ to get $b_2=-3; b_3=-5$ and so $10^1 + 10^2 + 10^4 + 10^5 = 110110$ is divisible by $7$.

Or we could to $a_3=2+6=8$ and $b_3=2$ so $10^1 + 10^2 + 10^8 = 100000110$ is divisible by $7$.

Of course if you get any $N$ divisible by $7$ then $10^k*N$ will also be divisible by $7$.