I have got a very specific mathematic/algorithmic problem. In fact, it is a an automata theory problem(buchi automaton), but this problem seems to be naturaly translated into a modular arithmetic problem.
Let $b\in\mathbb N^{>0}$ fixed, and $q$ a variable in $\mathbb N^{>0}$ coprime with $b$ and $i\in[1,q-1]\cap\mathbb N$ coprime with $q$ .
We can easily compute a value $N\in\mathbb N$ and a finite sequence $(u_n)_{n\in\mathbb[0,N-1]}\in[0,q-1]$ such that $u_0=i$ and $u_{n+1\mod N}\equiv u_n\times b\mod q$. Indeed, multiplication by $b$ modulo $q$ loops.
Let $p_n={(u_n*b-u_{n+1})\over q}$, that is we do the division of $u_n*b$ by $q$, $p_n$ is the quotient and $u_{n+1}$ the remainder, so $u_n*b=p_n*q+u_{n+1}$.
My problem is, I've got the $N$, $b$, and the sequence
$(p_n)_{n\in\mathbb[0,N-1]}$, is there some way for me to find if there exists a correct pair $(q,i)$ such that this is indeed the generated sequence $p_n$ ? And if this pair exists, to explicitely compute the pair ? (algorithmicaly, I would also need to know how big could $q$ be compared to the paramater.
I've got some reason to assume that the $q$ and $i$ are unique, as soon as we assume them to be coprime, (since the pair $(q,i)$ is an answer iff $(q\times c,i\times c)$ is an answer for any $c\in\mathbb N$.)
Let me give an example. I've got $b=10$ and the sequence $(0,4,7,6,1,9)$, then the answer is $(21,1)$, indeed \begin{eqnarray*} 1*10=10+0*21\\ 10*10=16+4*21\\ 16*10=13+7*21\\ 13*10=4+6*21\\ 4*10=19+1*21\\ 19*10=1+9*21 \end{eqnarray*} I don't know of any example of sequence such that I know for sure that there is no solution.
