What is the length of this sequence?

Question

Let $m>1$ be a prime number, and $k$ and $B$ be arbitrary elements of $\{0,1,\ldots , m-1\}$. Let $A\in \{0,1,\ldots , m-1\}$ such that $\gcd(A,m)=1$. For the following definition we use $\mod{m}$ to denote an operation and not an equivalence class. We define a sequence in the following way,

$$x_0=k$$ $$x_{n+1} = (Ax_n+B)\mod{m}.$$

What is the minimum value of $n>0$ such that $x_n=k$? In the case when $A=1$, it is clear that $n=\frac{m}{\gcd(m,B)}$ is the minimum $n$ such that $x_n = k$. This is because $\frac{mB}{\gcd(m,B)}$ is the LCM of $m$ and $B$. But I don't know how to take care of the case when $A>1$, any ideas?

lhf · Accepted Answer · 2018-05-18T01:32:23.773

2

If $A=0$, then the sequence is $k,B,B,\dots$, and so goes back to $x_0$ iff $B=k$. In this case, $n=1$.

If $A=1$, then the sequence is $k,k+B,k+2B,\dots$, and so goes back to $x_0$ after $n$ steps iff $nB\equiv 0 \bmod m$. In this case, $nB=lcm(B,m)$ and so $n=lcm(B,m)/B=m/\gcd(B,m)$, as you have found.

If $A\ne 0,1$, then take $C$ such that $(A-1)C \equiv B \bmod m$.

Let $y_n = x_n + C$. Then $y_{n+1}=Ay_n$ and so $y_n \equiv A^n y_0 \bmod m$.

If $y_0 \not\equiv 0 \bmod m$, then $y_n \equiv y_0$ iff $A^n \equiv 1 \bmod m$.

Therefore, the $n$ you seek is the multiplicative order of $A$ mod $m$. Unfortunately, there is no known formula for that.

If you settle for any $n$, not necessarily the minimal one, then $n=m-1$ works, by Fermat.

edited May 18 '18 at 01:32

answered May 18 '18 at 01:11

lhf

216,483

I will accept since you answered my original question. But I have more more question, in the case that $m$ is not prime, eulers theorem would suffice? Or could we do better? – ultrainstinct May 18 '18 at 01:39
If $m$ is not prime, Euler's theorem suffices but you can do better with Carmichael's function instead of $m-1$. – lhf May 18 '18 at 01:41

What is the length of this sequence?

1 Answers1