2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – Hans-Peter Stricker Dec 6 '18 at 17:04
  • $\begingroup$ wolframalpha.com/input/… and $\varphi(3^n) = 2.3^{n-1}$ @HansStricker $\endgroup$ – reuns Dec 6 '18 at 17:08
  • $\begingroup$ 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.) $\endgroup$ – Hans-Peter Stricker Dec 6 '18 at 17:24
  • $\begingroup$ $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 $\endgroup$ – reuns Dec 6 '18 at 17:28
  • $\begingroup$ 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. $\endgroup$ – Hans-Peter Stricker Dec 6 '18 at 17:31
1
$\begingroup$

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

enter image description here

enter image description here

enter image description here

$\endgroup$

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.