If we make a DFA accepting binary strings divisible by 4 then it takes 4 states such as
state 0 : remainder 0 accepting 4,8,12,16,20,24,28,32,36,40...
state 1: remainder 1 accepting 1,5,9,13,17...
state 2: reaminder 2 accepting 2,6,10,14,18...
state 3: remainder 3 accepting 3,7,11,15,19....
This DFA is also accepting all stings divisible by 8 also..Thus
GCD (4,8) = 4
Even this is a pattern for every question like this for any other number such as divisible by 3,6 will take GCD (3,6) states.
