Let Cn$=\{$w in $\{0,1,2\}$w is a number in base $3$ that is a multiple of n$\}$

$.$ For example, $2210$C$2$

but $2210$ in C$3$

$,$ since $2210$

in base $3$ is $75$

in base $10.$

Give a DFA for C$2$

$.$

Show that for all n

$,$ Cn

is regular by giving a DFA for it$.$

Hints:

As in Exercise $2,$ you must specify the DFA as a $5-$tuple that depends on n

$.$

You need only remember the current value of the number modulo n

$.$

Reading a $1$

changes the current value from K

to $3$K$+1$

$.$

If K

is some integer and k

is its value modulo n

$,$ then $3$K$+1$

is congruent to $3$k$+1$

modulo n