The procedure can be explained as follows: Scan the list of numbers and keep looking for the remainder of the string when divided by 3.

There are three cases (and states):

**When the remainder is zero:** When we are in this state, no matter how many zeros we add, we will get a remainder of zero. If we add a 1, then the remainder is 1 and it goes to state **1**
**When the remainder is one:** If we add **1,** then it is equivalent to multiplying the number by 2 and adding one – which means if we had x that had remainder 1, then now we have **(2x+1)%3**, which is equivalent to **3%3, **which is zero. Hence it goes to state **1.** When we add 0, then we multiply the number by 2, whence the remainder becomes 2 and it goes to state **2.**
**When the remainder is two:** If we add **0** to it, then we are multiplying the number by 2. When **x%3 **is 2, by simple arithmetic we can find that **(2x)%3** is 1, so it goes to state **1.** If we add 1 to it, then **(2x+1)%3** is 2 only (again by simple arithmetic) in which case it remains in state **2.**

Using this reasoning, we can construct a DFA to check for divisibility by any number.

### Like this:

Like Loading...

*Related*

Point2 line4: Hence it goes to state 1. It should have been 0. Nice article btw. Thanks