0
$\begingroup$

Computer scientist here looking at a question that came about from in-place matrix transposition, but rusty on my abstract algebra and number theory...

Suppose we have the multiplicative group $\mathbb{Z}/n\mathbb{Z}$ and some $k$ which divides $n + 1$, with $k > 1, n > 2$. If we look at the multiplication of $k$ against elements of $\mathbb{Z}/n\mathbb{Z}$, they will fall into cycles.

For example, if $k = 1$, then we will obviously get $n$ distinct cycles. For a non-trivial example, consider $\mathbb{Z}/11\mathbb{Z}$ and let $k = 4$. The cycles generated here are $\{0\}$, $\{1, 4, 5, 9, 3\}$, and $\{2, 8, 10, 7, 6\}$.

Two questions arise: Can we say anything about the number of cycles under this action? Given some element $m$ in $\mathbb{Z}/n\mathbb{Z}$, is there an efficient way to tell what cycle $m$ belongs to?

Thanks!

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ How are the cycles represented in order to tell what cycle $m$ belongs to? $\endgroup$
    – LeechLattice
    Commented Sep 27, 2019 at 9:20
  • 3
    $\begingroup$ I'm not sure to understand what is "the multiplicative group $Z/nZ$", as this is an additive group with an multiplication that does not make a group. Maybe you mean a multiplicative group that is cyclic of order $n$ ($\mu_n$ is a better notation), or the group of invertibles in $Z/nZ$. $\endgroup$
    – YCor
    Commented Sep 27, 2019 at 9:25
  • 3
    $\begingroup$ @YCor: I think the OP means neither of the two, but just the set $\mathbb{Z}/n\mathbb{Z}$ with the action given by multiplication by an invertible element $k$ modulo $n$. $\endgroup$
    – Tom De Medts
    Commented Sep 27, 2019 at 9:57
  • 1
    $\begingroup$ A (friendly) warning: the question is not about research level mathematics and normally it is more suitable for the "mathematics" site. People are being kind, so it still gets answered instead of put on hold. $\endgroup$
    – WhatsUp
    Commented Sep 27, 2019 at 15:56
  • $\begingroup$ @TomDeMedts: Yes, precisely, that was just an error in description on my part. $\endgroup$
    – Rory
    Commented Sep 27, 2019 at 18:22

1 Answer 1

Reset to default
3
$\begingroup$

Let $[a] = a +n\mathbb{Z}$ be an element of $\mathbb{Z}/n\mathbb{Z}$. Then the cycle of $[a]$ under the acttion of $k$ is $\{[ak^{r}] : r \in \mathbb{N} \}.$ The length of the cycle is $d$, where $d$ is the smallest positive integer such that $n$ divides $a(k^{d}-1).$ This depends somewhat on the factorization properties of $n$.

For example, if $n$ is prime, then only the cycle $[0]$ has length $1$, and every other cycle has length which is the order of $k + n\mathbb{Z}$ in the multiplicative group $U_{n}$ of units in $\mathbb{Z}/n\mathbb{Z}$.

More generally, whenever $a$ is coprime to $n$ (so that $a+n\mathbb{Z}$ is an element of $U_{n}$), the length of the cycle containing $[a])$ is again the order of $k + n\mathbb{Z}$ in the multiplicative group $U_{n}$ of units in $\mathbb{Z}/n\mathbb{Z}$).

However if ${\rm gcd}(a,n) = h > 1$ then the length of the cycle containing $[a]$ is instead easily checked to be the order of $k + \frac{n}{h}\mathbb{Z}$ in the multiplicative group $U_{\frac{n}{h}}$ of units in $\mathbb{Z}/\frac{n}{h}\mathbb{Z}$.

Note that in your example of $n = 11$ and $k = 4$, the order of $[4]$ in $U_{11}$ is $5.$

I am not sure what you are asking for in the second question. Perhaps you mean to ask "what is the length of the cycle containing $m$?". This is partially addressed by what I have written above.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks, this is exactly it! Is there some closed-form mathematical description of the order of $[k]$ in $U_n$? The second q is... Suppose I consider the elements of $\mathbb{Z}/n\mathbb{Z}$ in turn. And suppose I maintain a "visited" bit for each. $0$ is solo, $1$ leads through a cycle of $5$, the same with $2$. Now, as I consider $3, 4, 5, ...$ I'll see that I've flipped the "visited" bit for each element. This saves recomputing any cycle, but it comes at the cost of maintaining bits. Can I instead map each element to a canonical element of its cycle in such a way to avoid BOTH costs? $\endgroup$
    – Rory
    Commented Sep 27, 2019 at 18:31
  • $\begingroup$ Deciding whether all non-zero elements of $\mathbb{Z}/p\mathbb{Z}$ are in the same orbit under multiplication by $k$ is the same as deciding whether $k$ is a primitive root in the field. Such elements are easy to find computationally, but no characterisation of such elements is known. (E.g. it is not known for which primes $2$ is a primitive root.) Since we can't work out even the cycle structure in general, I don't think there's an efficient way to compute canonical representatives for each cycle. $\endgroup$
    – Padraig Ó Catháin
    Commented Sep 28, 2019 at 0:15

Not the answer you're looking for? Browse other questions tagged .