# Find the minimal period

Let $n$ be a positive squarefree number. Find the minimal period $t$ in terms of $n$ of the sequence $x_m$ where $x^m \equiv x_m \pmod{n}$ and $0 \leq x_m \leq n-1$.

Attempt:

To prove that $x_m$ is periodic with period $t$ independent of $x$, we see that it is sufficient to find the residues modulo every prime factor of $n = a_1 a_2 a_3 \cdots a_r$ where $a_1,a_2,\ldots,a_r-1$ are the prime factors of $n$ listed in ascending order. Then using Fermat's Little Theorem, $x^{a_i}\equiv x \pmod{a_i}$ and thus the periods of each of the modular congruences modulo $a_i$ is $a_i-1$. Thus, since the residues of $x^m$ will be the same as the residues of $x^{m+t}$, modulo each prime $a_i$, period $t = \text{lcm}(a_1-1,a_2-1,\ldots,a_r-1)$.

This is not the minimal period, but it is a period. How do I go about finding the minimal period?

Assume the prime factorization of $n$ is $n=p_1p_2\dots p_r$. Let $U=\{1,2,\dots, r\}$ and $V=\{1\leqslant i\leqslant r|\gcd (x,p_i)=1\}$. Then $U-V=\{1\leqslant i\leqslant r,p_i|X\}$. So, we divide $U$ into two disjoint parts.
If $V=\emptyset$, then we can check the period $t=1$, since $x^m\equiv 0(\mod n)$ for all $m\in\mathbb{Z}_{>0}$.
If $V\neq \emptyset$, for each $i\in V,$ let $h_i$ be order of $x$ modulo $p_i$. Let $t=\text{lcm}(h_i)$, $i\in V$. Then since $h_i|t$, we have $x^t\equiv 1(\mod p_i)$ for all $i\in V$. Hence $x^{m+t}\equiv x^m(\mod \prod_{i\in V}p_i)$ for all $m\in\mathbb{Z}_{>0}$.
For $j\in U-V$, we have $p_j|x$, thus $(\prod_{j\in U-V}p_j)|x$. Hence $(\prod_{j\in U-V}p_j)|(x^{m+t}-x^m)$ for all $m\in\mathbb{Z}_{>0}$.
Hence, we have $(\prod_{i\in V}p_i\cdot \prod_{j\in U-V}p_j)|(x^{m+t}-x^m)$. Thus $n|x^{m+t}-x^m$. Hence $x^{m+t}\equiv x^m(\mod n)$. $t$ is a period.$Now, we prove$t$is minimal. Assume$T$is a period, then$x^{m+T}\equiv x^m (\mod n)\Rightarrow n|x^{m+T}-x^m\Rightarrow (\prod_{i\in U}p_i)|x^m(x^T-1)\Rightarrow (\prod_{i\in V}p_i)|x^m(x^T-1)$. Note that for$i\in V$, we have$\gcd(p_i,x)=1$. Hence, we have$(\prod_{i\in V}p_i)|x^T-1$. Hence$x^T\equiv 1(\mod p_i)$for$i\in V$. By the definition of order, we have$h_i|T$for$i\in V$. Hence$\text{lcm} (h_i(i\in V))|T\Rightarrow t|T\Rightarrow T\geqslant t$. So, when$V\neq\emptyset$, the minimal period is$t=\text{lcm}(h_i)$, for$i\in V$, where$h_i$is the order of$x$modulo$p_i$for$i\in V$. • I don't think this is true. Take for example$x = 5 \cdot 7 = 35$and$n = 7 \cdot 11 = 77$. According to this,$V$is not empty but$t=2$. Does$\text{lcm}(h_i)=2$? – user19405892 May 30 '16 at 0:55 • Thanks for your comment.$35\equiv 35(\mod 77)$, but$35^3=42875\equiv 63(\mod 77)$. So, the period$t$is not 2. In this case,$V=\{11\}$, and the order of$35$modulo$11$is 10$. So, the period should be 10. – Qingzhong Liang May 30 '16 at 1:08
• You have found the minimal period in terms of $x$ and so for a particular $x$ value. We need to find the minimal period in terms of $n$ for all $x$. – user19405892 May 30 '16 at 4:21
• I see. My answer is the smallest period for each $x$. I think the period is depended on $x$. But if you want to find the minimal period $t$ such that it is the period for all $x$, we should look at the case such that all $h_i$ are maximal (i.e. $h_i=p_i-1$), in other words, $x$ is a primitive root for each $p_i$. And by Chinese Remainder Theorem, we know such $x$ always exists, then $t=\text{lcm}(p_i-1)$. So, you are correct. – Qingzhong Liang May 30 '16 at 5:18