I am reading about the dynamics of multiplication $\pmod m$ , and the totient function.
So from what I have understood, the totient function $\phi(n)$ is the cardinality of $\Phi(n)$ which is the set of elements between $1$ and $n - 1$ that are co-prime to $n$.
This totient function is apparently used to define the number of elements of $\Phi(n)$ of cycle-length $\lambda$.
Now I read that if we have a prime number $p$ the possible cycle lengths are the divisors of $p - 1$.
I have verified that as follows:
E.g for $p = 13$ the divisors of $12 = {1, 2, 3, 4, 6, 12}$
If we multiply by $3 \pmod {13}$ we have a cycle of length $3$ i.e.
1 -> 3 -> 9 -> 1
Or if we multiply by $5 \pmod {13}$ we have a cycle of length $4$ i.e.
1 -> 5 -> 12 -> 8 -> 1
I have tried with all the numbers up to $N-1 = 12$ and the cycle lengths are as follows:
| $a^x \pmod {13}$ | $\lambda$ |
|---|---|
| $2$ | 12 |
| $3$ | 4 |
| $4$ | 6 |
| $5$ | 4 |
| $6$ | 12 |
| $7$ | 12 |
| $8$ | 4 |
| $9$ | 3 |
| $10$ | 6 |
| $11$ | 12 |
| $12$ | 3 |
Now I can see that indeed all the cycle lengths are divisors of $N - 1$.
I also can see that there are $\phi(12)=4$ primitive roots.
What I can't understand is why are the lengths always divisors of $12$ and how come $\phi(\lambda)$ will indeed show me the number of elements of $\Phi(N)$ with length $\lambda$ but the corresponding $\Phi(\lambda)$ does not contain those elements.
E.g. as mentioned:
$\Phi(12) = {1, 5, 7, 11}$ and indeed we have $4$ elements of $\Phi(13)$ with cycle length $\lambda = 12$ but those are: $2, 6, 7, 11$.
Could someone please help me understand the concepts and intuition here?
Also are the ideas different if $m$ was a composite instead of prime?
Update:
So I thought about it a bit, and I came to the following conclusion:
For each $a \in {1..N-1}$ we have a cycle length $\lambda$ and for $N = 13$ we can see in the table above the various lengths.
Now unless $\lambda = N - 1$ which happens only for primitive roots, we have more than $1$ cycle for each number e.g. $c$ to indicate the number of cycles.
Since all the numbers must appear to a cycle, it must be that:
$c \cdot \lambda = N - 1 \implies c \mid (N - 1) \And \lambda \mid (N - 1)$
but this means that the length is always a divisor of $N - 1$.
Assuming I got this part right, it is still not clear to me how the totient can give the proper length even if the contents of the relevant set are completely different
The existence of the primitive root $r$ shows to us that we can think of the elements that are coprime to $p$ as $r,r^2,\dots,r^{p-1} = 1$.
It follows that multiplication between two elements is just the same as adding the exponents $\bmod p-1$.
So now we just need to consider $\mathbb Z_{p-1}$ under adition and look at the orders, the order of an element $a$ is equal to $\frac{p-1}{gcd(a,p-1)}$ and so the ones with order $p-1$ are the ones that are coprime to $p-1$.
If $n$ is not prime then you can still determine the group structure of the multiplicative group of $\mathbb Z_n$ by using the chinese remainder theorem on each prime power factor. It turns out that the multiplicative group of $\mathbb Z_{p^k}$ is cyclic for odd $p$ and is $\mathbb Z_2 \times \mathbb Z_{2^{k-2}}$ when $p$ is $2$. So by the chinese remainder theorem the group structure is just the direct product of those groups, and you can determine the number of elements of each order using this factorization.