# Prove that a DFA will transition to the same state after $\gcd(i,j)$ steps where $i$ and $j$ steps can be taken to reach that state

Suppose $M=(Q,\Sigma,\delta,q_0,F)$ is a deterministic finite automaton, and suppose there exists a state $q \in Q$, a string $z \in \Sigma$, and integers $i,j>0$ such that $\delta(q,z^i)=\delta(q,z^j)=q$. Prove that $\delta(q,z^{gcd(i,j)})=q$

I can intuitively say that starting from a state $q$ if you take $x$ steps on a DFA to reach the same state and at the same time $y$ steps also takes the DFA to the same state, then there exists a cycle that is repeated $\gcd(x,y)$ times to reach the same state again and again. Is this correct for a DFA? How can I prove this formally?

• @ratchetfreak For the language that you gave, you must consider a DFA that recognize it, not the language itself. The claim talks about implementations, not semantic. – Abdous Kamel Nov 24 '17 at 13:30
• The comment refers to a deleted comment. I have now deleted my own comment as well. – Yuval Filmus Nov 24 '17 at 15:26

Consider the sequence $q(n) = \delta(q,z^n)$ for $n \geq 0$. Let $b$ be the smallest index so that $q(a) = q(b)$ for some $a < b$. It is not hard to check that all further iterates cycle through the values $q(a),\ldots,q(b-1)$. Since we are given that $q(i) = q(0)$, it follows that $a = 0$, and so the function $\pi$ on $\{q(0),\ldots,q(a-1)\}$ defined by $\pi(q') = \delta(q',z)$ is a cyclic permutation.
We are given that $\pi^i(q) = \pi^j(q) = q$. Since $\pi$ is a permutation, also $\pi^{-i}(q) = \pi^{-j}(q) = q$. It follows that for any integer $\alpha,\beta$ (not necessarily non-negative) $\pi^{\alpha i + \beta j}(q) = q$. In particular, Bezout's identity shows that $\pi^{\operatorname{gcd}(i,j)}(q) = q$, and so $\delta(q,z^{\operatorname{gcd}(i,j)}) = q$.