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

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

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

• Would you mind to help me to align your answer with the special case 49:243 as depicted in my question? (It's not too obvious how to start off.) – Hans-Peter Stricker Dec 6 '18 at 17:04
• wolframalpha.com/input/… and $\varphi(3^n) = 2.3^{n-1}$ @HansStricker – reuns Dec 6 '18 at 17:08
• This looks promising, but (i) What does $2.3^{n-1}$ mean? Should it be $2\cdot 3^{n-1}$? and (ii) I'm looking for an expression with a variable which I can set to $243$. (Actually I see only a variable which I can set to $49$. And $243$ comes only in the result.) – Hans-Peter Stricker Dec 6 '18 at 17:24
• $3^n$ are the divisors of $243$ and $\varphi$ is the Euler totient. Do you understand how multiplication by 49 acts on the group of integers coprime with $243$ ? @HansStricker – reuns Dec 6 '18 at 17:28
• I know the symbol and meaning of the Euler totient. And now I see: $3^1 = 3$, $3^2=9$, $3^3 = 27$, $3^4 = 81$, $3^5 = 243$ are exactly the divisors of $243$. That's interesting enough, I was not aware of. – Hans-Peter Stricker Dec 6 '18 at 17:31

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