For any square-free $n \geq 1$ and $a \in \Bbb{Z}/n$ including $\gcd(a,n) \neq 1$, then in the list $a, a^2, a^3, \dots$ either $a$ or $a^2$ repeats?

Question

For example, modulo $30$ we have that $\gcd(5, 30) = 5$, but $5, 5^2, 5^3 = 5, 5^2, \dots$ goes the list, so both repeat.

We know it's true when $\gcd(a,n) = 1$ because a cyclic group is formed in $\Bbb{Z}/n^{\times}$, s it's sufficient to prove the case when $\gcd(a, n) = d \neq 1$.

Another example:

$$ n = 15:\\ 3, 3^2, 3^3=-3,-3^2,(-3)^2=3^2, \dots \\ 6,6,6, \dots \\ 9,9^2=6,9, \dots\\ 5,10,5,10, \dots\\ $$

Is this hopelessly difficult to prove?

Answer 1

By the Chinese Remainder theorem, $\mathbb{Z}_n$ is a product of $\mathbb{Z}_{p_i}$ for prime $p_i$, and we can view $a$ as an element of $\prod_i \mathbb{Z}_{p_i}$, $(a_1,a_2,\dots,a_k)$. For any of the component rings, $\mathbb{Z}_{p_i}$, we have that the sequence $a_i^m$ must repeat either with period $1$ (if $a_i = 0$) or with period dividing $p_i-1$ (otherwise). Take the lcm of the periods of all the $a_i^m$ sequences for all the component rings and you'll get the period for the product ring. So $a^m$ always repeats.