Show that the language is regular

[mathmari]

Hey!

Let $$C_n=\{x \ \mid \ x \text{ is a binary number that is a multiple of } n\}$$

Show that for each $n \geq 1$, the language $C_n$ is regular. Could you give me some hints how we could show that??

Do we have to construct a NFA that accepts the language??

 

[Evgeny.Makarov]

Let the set of states be $0,\dots,n-1$, i.e., possible remainders when a number is divided by $n$. Think about how the remainder changes when a number is read digit by digit right to left.