math - Divide Binary Numbers FSM

Question

Note: this question can be solved by math experts too.

Today I learnt about FSM, My lecturer said for example if we are given a number in binary (being inserted from its MSB to LSB) we can decide if it's divisible by 7 using 7 states where each state indicates the remaining part.

But:

1. How can I decide when to move from one state to the other?

2. My professor said that for General number not always we need N states to decide if it's dividable by N or not, can someone please give me an example of such special case?

question from:https://stackoverflow.com/questions/65876843/divide-binary-numbers-fsm

Answer 1

1. Work it out on paper. You have seven states, {0, 1, ... 6} for the possible remainders. Suppose the machine is in state 4; the remainder is 4. Then it receives the next bit, which is 1. Now what is the remainder? (Answer: 2) You must assign all fourteen of these transition rules.

2. Try it for n=6. You will see that there is no need for a state 4, since it is identical to one of the other states.