Cycle structure of the permutation $x \mapsto p·x\operatorname{mod}q$ for coprime $p,q$

Question

Let $[q] = \{0,\dots,q-1\}$, $p < q$.

Consider the function $\mathbf{p}: [q] \rightarrow [q]$ which sends $x \mapsto p·x\operatorname{mod}q$, i.e. the multiplication by $p$ modulo $q$ on $[q]$.

One finds that when $p$ and $q$ are coprime, $\mathbf{p}$ is a permutation of $[q]$ with $\mathbf{p}(0) = 0$.

Each such permutation – depending solely on $p$ and $q$ – has a specific cycle spectrum: $n_m$ cycles of length $m$.

How do I calculate the possible cycle lengths $m$ and their corresponding numbers $n_m$ just by looking at $p$ and $q$?

Answer 1

Let $H_q = \{ p^n \bmod q,n \ge 0\}$, it contains $|H_q| = $ "the order of $p\bmod q$" elements.

• Assume $\gcd(a,q)=1$ then $a \in (\mathbb{Z}/q\mathbb{Z})^\times$ so $|aH_q| = |H_q|$

• Otherwise let $g = \gcd(a,q)$. Then $\frac{a}{g} \in (\mathbb{Z}/q\mathbb{Z})^\times$ and $|a H_q|= |g \frac{a}{g} H_q|=|g H_q| = |g H_{\frac{q}{g}}| = |H_{\frac{q}{g}}|$

• Thus for each $d = \frac{q}{g} | q$ there are $\frac{\varphi(d)}{|H_{d}|}$ cycles of length $|H_{d}| = $ the order of $p \bmod d$

• To know the order of each $p \bmod d$, you can factorize $q = \prod_j p_j^{e_j}$ and compute the order of $p \bmod p_j^m,m \le e_j$, then $|H_{\prod_j p_j^{m_j}}|$ is the $lcm$ of the $|H_{p_j^{m_j}}|$

Answer 2

Having digested and finally understood user reuns' answer, let me share some visual examples: