# Is a language containing set of binary numbers which are divisible by number N Regular?

Let N be any positive integer, then is following language regular for every $N$?

$L$ = { $B_n : B_n(modN) == 0$ } where $B_n$ is binary representation of a number.

E.g, $L=\lbrace B_n : B_nmod31 == 0,B_n \ is \ a \ binary \ number \rbrace$ is regular? Will the language be regular for any positive number in place of $31$.

You can produce a finite automaton to recognize binary strings divisible by $N$ for any $N>0$. Use $N+1$ states, $s$ (the start state) and $q_i$, where being in state $q_i$ corresponds to having seen input $B$ which is congruent to $i\bmod N$.
The transitions are then easy enough: in state $q_i$ and seeing a $0$ input the machine would pass to state $q_k$, where $k\equiv 2i\bmod N$, since appending a zero to a binary string doubles the number represented. Similarly $\delta(q_i, 1)=q_k$, where $k\equiv 2i+1\bmod N$.
The start state is there solely to avoid the question of what number the empty string represents, and obviously $q_0$ is the final state.
• @Tamas. Try it for $N=3$ to see what's going on. The only strings in the language are precisely those representing numbers divisible by 3, in this case – Rick Decker Dec 13 '17 at 13:46