# DFA that accepts any integer $n$ such that $n \bmod 7 =1$

It seems impossible for me to find a pattern for integers $$n$$ such that $$n \equiv 1 \quad(\bmod 7)$$ in order to construct this DFA.

Is there smart way to do it without a machine which has memory or completes operations? A hint would be greatly appreciated.

• How are your integers $n$ encoded? Try to be as explicit as possible, since the answer would heavily depend on the details of the encoding. – Yuval Filmus Oct 25 '18 at 20:52
• A DFA has memory. It's called the "state". You need 7 states, just below 3 bits. – gnasher729 Oct 27 '18 at 10:12

I assume you are talking about integers encoded in some base $$b \geq 2$$, and we're reading the integer from left to right.

An inductive hint: say we have read the number $$n$$ so far, and our inductive assumption is that we are in state $$n \bmod 7$$ (so we have 7 states). We read the digit $$d$$. Our next state should be $$bn + d \bmod 7$$. How do we correctly determine what state to go to, since we don't know $$n$$?

Well the trick is that while you don't know $$n$$, you do know $$n \bmod 7$$. And:

$$bn + d \equiv b(n \bmod 7) + d\mod 7$$

So for example, in base $$10$$, if we are in the state $$3$$ (meaning $$n \equiv 3 \mod 7$$) and we just read the digit $$8$$, our next state will be $$10\cdot 3 + 8 \equiv 3 \mod 7$$. In other words, state $$3$$ points to itself on reading digit $$8$$ in base $$10$$.

Place 7 nodes. Number them from 0 to 6. In Any time, in whatever node we are, represents the current number module 7. So starting node is 0. And note 0 is the accepting node.

For each node, there are 7 outgoing edges (from 0 to 6.) Say we are in node i; outgoing edge j from i, connects the node i to node (i*10+j) mod 7.