Minimum Number of States in a DFA accepting a binary number divisible by 'n'

Question

Lets first prove the number of states in the minimal DFA for accepting binary strings divisible by a given number say $12$

We need $3$ states for checking if a binary number is divisible by $3$ - each state corresponding to remainders $0,1,2.$ Here, remainder $0$ will be the final state for divisibility by $3$. If we add a '0' transition from this state to another state and make it FINAL, we get divisibility by $6$ as a '0' at end ensure number is divisible by $2$ and also retains the property that the number is divisible by $3$ which makes it divisible by $6.$ Add one more state like this and we get numbers divisible by $3\times 2\times 2 = 12.$ Thus we need $5$ states in the minimal DFA for divisibility by $12.$

---

The above construction works because in the DFA for divisibility by $3$, there will be no outgoing edge on $0$ to the final state from any other state. This is because no number not divisible by $3,$ when multiplied by $2$ will become divisible by $3$ (holds for any odd number). But there will be self edge on the final state for '0' - when we add the new state for divisibility by $6,$ we remove this edge and make it go to the new FINAL state. 

---

The above construction works in general too. To check if a binary number is divisible by $n$

1. If $n$ is a power of $2$ we need $\log_2 n+1$ states in the minimal DFA 
2. If $n = 2^k \times m,$ where $m$ is odd, then we need $k + m$ states in the minimal DFA

PS: To be proved: To check a binary number for divisibility by any odd number $k$ requires $k$ states in the minimal DFA.

---

To find the minimal number of states in the DFA accepting binary strings divisible by $m$ and $n:$

Here, we have to check divisibility by $m$ and divisibility by $n$. So, we can take this as divisibility by $\text{LCM}(m,n).$

---

To find the minimal number of states in the DFA accepting binary strings divisible by $m$ or $n:$

Comments

Thanks for this post.

---

Amazing work Sir

---

Here is the way I have tried to prove that To check a binary number for divisibility by any odd number k requires k states in the minimal DFA.

 

Note that any binary number $abcd = (ab)2^2 + cd; abc = (ab)2^1 + c$

In general, $a_na_{n-1}\dots a_1 = (a_na_{n-1 \dots a_{x+1}})2^x + (a_xa_{x-1} \dots a_1)$

Theorem 1 : If a divides pq and is relatively prime to p then it divides q.

http://www.math.ubc.ca/~cass/courses/m446-03/divisibility.pdf

Proof :

Statement : Language of binary numbers divisible by any odd number n requires n states in the minimal DFA.

The way to prove such results is to twofold: first we prove an upper bound by constructing a DFA accepting the given language(that is n), then we prove a lower bound using Myhill–Nerode theory.

Now I'll prove, by Myhill Nerode Theorem that if n is odd number then All the numbers from 0 to n-1 will be mutually distinguishable.

Note that 0 is already distinguishable from 1 to $n-1$. So, we only need to show that All the numbers from 1 to n-1 will be mutually distinguishable.

By Myhill nerode theorem, two strings u and v are distinguishable if and only if there is some string w such that exactly one of uw, vw belongs to our language. 

Take any string $u$ whose decimal value is $a ; 1 \leq a \leq n-1$ , We will add append some string $v$ to $u$ such that uv belongs to our language i.e. $decimal(uv)$ is multiple of $n$. Let $decimal(v) = m$ and let $|v| = i$

So, $a(2^i) + m = n(X)$ 

Now, take any $b; 1 \leq a < b \leq n-1$ different from $a$ i.e. $a \neq b$ 

 $m = n(X) - a(2^i)$

We will show that for ALL $i \geq 1$, $b(2^i) + m $ is Not multiple of $n.$

Let's check $b(2^i) + m $ 

= $b(2^i) +  n(X) - a(2^i)$ = $2^i(b-a) + n(X)$

$2^i(b-a) + n(X)$ is Not divisible by n. Because $2^i(b-a)$ is Not divisible by n due to the Theorem 1 (NOTE that $1 \leq b-a \leq n-1$ and $i \geq 1$,  ) 

 

So, this proves that If you take any Two binary strings $u,v$ whose decimal value is between 1 and n-1 and $decimal(u) \neq decimal(v)$ then for ALL strings $w \neq \epsilon$ if  $uw \in L$ then $vw \notin L.$

This shows that every number from 0 to $n-1$ is mutually distinguishable. 

 

 

 

 

 

---

To find the minimal number of states in the DFA accepting binary strings divisible by mm or n:

what is the answer to this part.

---

@arjun sir please answer this.

---

answer will be LCM(m,n)
We only have to change all the multiples of m, n and LCM(m,n) to final state.