What can be a generalization of repeats in exponentiation using modulo?

Question

I came across a Math Problem in a Japanese Coding Test(It is officially over now so no worries about discussing it, https://atcoder.jp/contests/abc179/tasks/abc179_e).

I will write the mathematical version of this problem.

Let $A$ be a sequence that is defined by the initial values $A_1=x $ and this recurrence relation is given $A_{n+1}$=$(A_{n}^2)$ $mod$ $M$ where $M$ can be any natural number.

Find $\sum_{i=1}^{i=N}A_{i}$

I will tell what I have deduced till now:

1. If I write this recurrence in equation it demands us to find $(x^1 mod M + x^2 mod M + x^4 mod M + x^8 mod M + x^{16}mod M ..$ till $n$ terms).
2. If We take any example for $x=2$ and $M=1001$ the values of this series come out to be like this $2,4,16,256,471,620,16,256,471,620....$ and this block of $16,256,471$ repeats.
3. I observed that for any given $x$ and $M$ the series formed will come at a point where one of it's window will start repeating, just like in the above case this window of $16,256,471$ repeated after certain point. All because of Modulo Magic I have observed that it will repeat but I don't have any proof of How and Why ?
4. I tried using Fermat's Little theorem that for the case of when $M$ is prime maybe of some use But didn't find an apt conclusion to it.

Now I am stuck at this problem that How will Modulo work in such kind of series and how Will the values of this series depend on different versions of $x$ and $M$ like them being co prime to each other or otherwise. and if this series is to give recurring values after a certain point then Why and How and also as it happened in the example case I have given All the values do not repeat due to this kind of exponentiation but only a window repeats,I don't understand why.

Answer 1

First, consider the case where $x$ and $M$ are coprime, i.e., $\gcd(x,M) = 1$. Since for all $i \gt 1$ we have $0 \le A_i \lt M$, there are only a finite # of values it can have so the sequence will eventually have to start repeating. Let $j$ and $k$, where $j \lt k$, be the first indices where the values repeat. Since $x$ and $M$ are coprime, $x$ has a multiplicative inverse. Using this, we thus have

$$\begin{equation}\begin{aligned} x^{2^{k-1}} & \equiv x^{2^{j-1}} \pmod{M} \\ x^{2^{k-1}} - x^{2^{j-1}} & \equiv 0 \pmod{M} \\ x^{2^{j-1}}\left(x^{2^{k-1} - 2^{j-1}} - 1\right) & \equiv 0 \pmod{M} \\ x^{2^{k-1} - 2^{j-1}} - 1 & \equiv 0 \pmod{M} \\ x^{2^{j-1}\left(2^{k-j} - 1\right)} & \equiv 1 \pmod{M} \end{aligned}\end{equation}\tag{1}\label{eq1A}$$

The multiplicative order of $x$ modulo $M$, i.e.,

$$m_1 = \operatorname{ord}_{M}(x) \tag{2}\label{eq2A}$$

must divide $2^{j-1}\left(2^{k-j} - 1\right)$. Let $a$ be the largest power of $2$ which divides $m_1$, so we have

$$m_1 = 2^{a}b, \; \gcd(b, 2) = 1 \tag{3}\label{eq3A}$$

The smallest value of $j$ which works is where $j - 1 = a \implies j = a + 1$, except where $a = 0$ and $x \ge M$, in which case we get $j = 2$ instead. This is the main reason why not all of the initial values repeat (i.e., where $a \gt 0$) but, instead, just a "window" starting at this minimum $j$ value.

Next, if $b = 1$, the smallest value of $k - j$ is $1$, else for $b \gt 1$, it's $m_2$ where

$$m_2 = \operatorname{ord}_{b}(2) \implies 2^{m_2} = kb + 1, \; k \in \mathbb{N} \tag{4}\label{eq4A}$$

With your example of $x = 2$ and $M = 1001$, the values start repeating with $j = 3$ and $k = 7$ giving $2^{j-1}\left(2^{k-j} - 1\right) = 4(15) = 60$. As you can confirm, in this case, $m_1 = 60$, although they will not in general be equal (since equality only occurs with $k = 1$ in \eqref{eq4A}).

Next, consider the somewhat more complicated case where $x$ and $M$ are not coprime. Let

$$q = \prod_{i=1}^{n}p_i \tag{5}\label{eq5A}$$

be the product of all of the $n$ primes $p_i$ which are factors of both $x$ and $M$. Splitting $x$ and $M$ into factors which aren't and are coprime with $q$ gives

$$x_1 = \prod_{i=1}^{n}p_i^{s_i}, \; x = x_1x_2, \; \gcd(x_2, q) = 1 \tag{6}\label{eq6A}$$

$$M_1 = \prod_{i=1}^{n}p_i^{t_i}, \; M = M_1M_2, \; \gcd(M_2, q) = 1 \tag{7}\label{eq7A}$$

Also, note $\gcd(x_2, M_2) = 1$ since they don't have any prime factors in common.

As before, let $j \lt k$ be the first indices which repeat. We split the congruence equation to that with $M_1$ and with $M_2$. This first gives

$$\begin{equation}\begin{aligned} (x_1x_2)^{2^{k-1}} & \equiv (x_1x_2)^{2^{j-1}} \pmod{M_1} \\ (x_1x_2)^{2^{j-1}}\left((x_1x_2)^{2^{k - 1} - 2^{j-1}} - 1\right) & \equiv 0 \pmod{M_1} \end{aligned}\end{equation}\tag{8}\label{eq8A}$$

Since no $p_i$ in $q$ from \eqref{eq4A} divides $(x_1x_2)^{2^{k - 1} - 2^{j-1}} - 1$, this means all factors of $p_i$ are in $(x_1x_2)^{2^{j-1}}$. In particular, the smallest possible $j$ requires, using \eqref{eq6A} and \eqref{eq7A}, that

$$2^{j-1}(s_i) \ge t_i, \; \forall \, 1 \le i \le n \tag{9}\label{eq9A}$$

Next, since $\gcd(x, M_2) = 1$, we have the same situation as at the start of this solution, with $M$ replaced by $M_2$, i.e., we get basically the equivalent of \eqref{eq1A} giving

$$x^{2^{k-1}} \equiv x^{2^{j-1}} \pmod{M_2} \implies x^{2^{j-1}\left(2^{k-j} - 1\right)} \equiv 1 \pmod{M_2} \tag{10}\label{eq10A}$$

We thus proceed as we did before, but with the added restriction now that $j$ must be at least as large as what's required by \eqref{eq9A}.