Minimum number of states in dfa accepting binary number with decimal equivalent divisible by $n$

Question

I was aware of the fact that, if DFA needs to accept binary string with its decimal equivalent divisible by $n$, then it can have minimum $n$ states.

However recently came across following text:

• If $n$ is power of $2$
  Let $n=2^m$, so number of minimum states $=m+1$. For $n=8=2^3$, we need $3+1=4$ states.
• Else If $n$ is odd
  Number of states $=n$. For $n=5$, we need $5$ states.
• Else if $n$ is even
  Keep dividing it with $2$ until you get odd quotient. The result is final odd quotient plus number of divisions done. For $n=20,20/2=10,10/2=5→5+2=7$ states

I was guessing:
Q1. From where all these facts came. (I know this must have come from general pattern that such DFAs follow, but then I have below doubts)
Q2. Are these points indeed correct?
Q3. If yes (for Q2), then what can be the reason for each point?
Q4. Do these three bullet points cover all cases? (I guess yes, since there is even and odd, but I am new to this, and I was guessing if any such more point is left unmentioned in my textbook, especially since I did not find any reference book (by Peter Linz and Hopcroft-Ullman) talking about this topic)

Answer 1

Case 1: $n$ is a power of 2

If you wanted to check whether a decimal number is divisible by some power of 10, you can just look at the number of trailing zeros. For example, all numbers that are divisible by $100 = 10^2$ end with 2 zeros (this is of course including numbers ending with more than 2 zeros). The same idea can be applied here for binary numbers and powers of 2. Specifically to check for multiples of $n = 2^m$, you can simply check if the string ends in $m$ zeros. For example, if $n = 16 = 2^4$, all multiples of $n$ will end in 0000 (4 zeros). Thus we can create the following DFA for $n = 16$:

This construction can be extended to all multiples of 2, where you have $m+1$ states to ensure that your input ends in at least $m$ zeros (reading a 0 takes you one state forward, reading a 1 takes you back to the start). As suggested in the comments on your question, you can show that you can't do any better than this using a Myhill–Nerode argument.

Case 2: $n$ is odd

The general idea here is that when a number is divided by $n$, the possible remainders are $0, 1, \ldots, n-2$ or $n-1$. We can give our DFA one state for each of these possible remainders so as we process a string, we're keeping track of the remainder of what we've read so far and transitioning to the appropriate remainder based on what character we read. Then, we accept if we finish in the remainder 0 state.

Design DFA accepting binary strings divisible by a number 'n' walks through a detailed method for constructing such a DFA, and you can find out more about this by searching for "DFA based division". This gives a total of $n$ states, which is optimal by Myhill-Nerode because these remainders are exactly the equivalence classes given by the relation $\equiv_L$ for the language $L = \{\text{binary strings divisible by }n\}$.

Case 3: $n$ is even (and not a power of 2)

The technique in case 2 also works here but it isn't optimal. Every $n$ in this case can be expressed as $2^km$ where $m$ is odd (this is the division procedure described in your question). Thus, to check whether a binary string is divisible by $n$, we check whether it is divisible by both $2^k$ and $m$.

We know that it takes $k$ states to check divisibility by $2^k$ (case 1) and $m+1$ states to check divisibility by $m$ (case 2). We can take a DFA for divisibility by $m$, unmark the accepting state and make it the start state for a DFA for divisibility by $2^k$, giving our final DFA $k+m$ states.

As an example, here's the DFA for $n = 6$:

The top three states ensure that the number is a multiple of 3, and the final accept state ensures that it is a multiple of 2.