2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Gerry Myerson Sep 20 at 0:23
  • $\begingroup$ 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. $\endgroup$ – Kartik Bhatia Sep 20 at 8:20
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – Kartik Bhatia Sep 20 at 8:19
  • $\begingroup$ The first paraghraph is not clear: multiply both sides of what, and what product? $\endgroup$ – Bill Dubuque Sep 20 at 8:22
  • $\begingroup$ @BillDubuque can you help me in this question ? $\endgroup$ – Kartik Bhatia Sep 20 at 12:24
  • $\begingroup$ @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. $\endgroup$ – John Omielan Sep 20 at 14:07
  • $\begingroup$ @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. $\endgroup$ – John Omielan Sep 20 at 14:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.