Question 60

1. Reachable residues: Since $7$ is prime and every symbol in $\Sigma = \{1, 2, 3, 4\}$ is non-zero modulo $7$, $prod(x) \bmod 7$ can only take values in the multiplicative group $(\mathbb{Z}/7\mathbb{Z})^\times = \{1, 2, 3, 4, 5, 6\}$ (residue $0$ is unreachable). Furthermore, $3 \in \Sigma$ is a primitive root modulo $7$ ($3^1 \equiv 3, 3^2 \equiv 2, 3^3 \equiv 6, 3^4 \equiv 4, 3^5 \equiv 5, 3^6 \equiv 1 \pmod 7$), so all $6$ non-zero residues are reachable from the initial state $prod(\epsilon) = 1$.
2. Pairwise distinguishability: For any two distinct residues $r_1 \not\equiv r_2 \in \{1, 2, 3, 4, 5, 6\}$, choose $k \in \{1, \dots, 6\}$ such that $r_1 \cdot 3^k \equiv 2 \pmod 7$ (using string $z = 3^k \in \Sigma^*$). Since $\gcd(3^k, 7) = 1$, we have $r_2 \cdot 3^k \not\equiv 2 \pmod 7$, so $z$ distinguishes $r_1$ and $r_2$.

By the Myhill-Nerode Theorem, the minimum-state DFA for $L$ has exactly $6$ states.