# DFA that accepts decimal representations of a natural number divisible by 43

First, I have tried to build a DFA over the alphabet $\sum = \{0,\dots, 9\}$ that accepts all decimal representations of natural numbers divisible by 3, which is quite easy because of the digit sum. For this I choose the states $Q = \mathbb{Z}/3\mathbb{Z}\cup\{q_0\}$ ($q_0$ to avoid the empty word), start state $q_0$, accept states $\{[0]_3\}$ and $\delta(q, w) =\begin{cases} [w]_3 &\mbox{if } q = q_0 \\ [q + w]_3 & \mbox{else } \end{cases}$

Of course, it doesn't work that way for natural numbers divisible by 43. For 43 itself, I would end in $[7]_{43}$, which wouldn't be an accepting state. Is there any way I can add something there or do you have other suggestions on how to do this? Thanks.

-

## migrated from cstheory.stackexchange.comJan 20 '13 at 8:58

This question came from our site for theoretical computer scientists and researchers in related fields.

Maybe you could use the divisibility test for 43: savory.de/maths1.htm . Or perform actual division using the DFA. In either case, the DFA would be very complicated. Any reason why you want to do this? –  Paresh Jan 20 '13 at 9:15
Your question is a special version of that one. –  A.Schulz Jan 20 '13 at 10:58

If the string read has a certain decimal value, then reading the next digit changes that value: multiply by $10$ and add that digit. The DFA keeps track of that value modulo $43$. Thus, for $q\in \{0,1,\dots,42\}$ and $a\in \{0,1,\dots,9\}$ you do
$\qquad \delta(q,a) = (10\cdot q + a) \bmod 43$.