0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – user19405892 May 30 '16 at 0:55
  • $\begingroup$ 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. $\endgroup$ – Qingzhong Liang May 30 '16 at 1:08
  • $\begingroup$ 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$. $\endgroup$ – user19405892 May 30 '16 at 4:21
  • 1
    $\begingroup$ 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. $\endgroup$ – Qingzhong Liang May 30 '16 at 5:18
  • $\begingroup$ Also, what if the order doesn't exist? Then this argument doesn't hold. We need to cover that as well. $\endgroup$ – user19405892 Jun 3 '16 at 18:42

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.