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

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.

• Since there are only finitely many values available modulo $M$ there must eventually be a value that has already come up previously. Since each value depends only on the previous value, once a value comes up a second time the sequence must repeat what it did the first time that value came up, periodically, forever. – Gerry Myerson Sep 20 at 0:23
• Yes I agree to that But why is it that only a certain value will repeat ? Why for the example I am taking it repeated after 16 not with 2. – Kartik Bhatia Sep 20 at 8:20

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}.

• It is taking me some time understanding it ! I didn't know about multiplicative order , I am clear with the case of them being co prime how are you dealing with other case Why does gcd come into play ? – Kartik Bhatia Sep 20 at 8:19
• The first paraghraph is not clear: multiply both sides of what, and what product? – Bill Dubuque Sep 20 at 8:22
• @BillDubuque can you help me in this question ? – Kartik Bhatia Sep 20 at 12:24
• @BillDubuque Thanks for the feedback. You're right it wasn't particularly clear. I've changed it by removing describing what I was going to do in my $(1)$ and, instead, just did it there. I believe this is now easier to understand. – John Omielan Sep 20 at 14:07
• @KartikBhatia As I commented to Bill, I've changed my first part dealing with my $(1)$. As for why the gcd (greatest common factor) comes into play, it's mainly due to the simpler handling in my $(1)$ can only occur when $x$ & $M$ are coprime. This is since a multiplicative inverse, i.e., a $y$ where $xy \equiv 1 \pmod{M}$, only exists for those cases. As I show in my $(8)$ & $(9)$, non coprime values have an added requirement of common prime factor powers in $x^{2^{j-1}}$ needing to be at least as large as in $M$. Please let me know if there's anything specifically I can explain further. – John Omielan Sep 20 at 14:19