Automata to detect numbers divisible by $7$

Question

I have a task and I really have no idea how to solve it.

Build deterministic finite automata such that it can detect numbers divisible by $7$.

So our alphabet is $\left\{0,1,2,3,4,5,6,7,8,9\right\}$

Our input is for example: $700$ - out automata should detect it.

Could you help me?

Answer 1

Hint:

If input string is in reverse order, you had better make use of the following property: $$n^{\phi(m)}\equiv 1\pmod{m}, \quad \mathrm{if}\ (m,n)=1,$$ where $\phi(m)$ stands for the Euler's totient function.

In this specific case, $(10,7)=1$. Let the nodes of your DFA represent 2-tuples of current positions (mod $\phi(7)$ of course) and residue classes (mod $10$).

More:

In a general sense, it is easier to build a NFA that reads numbers from the most insignificant digit, since the base $n$ (in this case, $10$) and the divisor $m$ (in this case, $7$) do not necessarily coprime.