Relation of totient, cycle length of multiplication and divisors 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
 A: 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.
A: Firstly note:
$$x^{2k}=(-x)^{2k}$$
While it may seem at first trivial, it means in mod, that if $x$ has even order, then $-x$ will have at most that order. Noting that : $$x^{2k+1}=-((-x)^{2k+1})$$ and $$(-1)^2=1$$  we see if $-1$ shows up somewhere on either path at any position, the other path has at most twice that length.
To have an order at all ( and not merely a cycle length) , $a$ and $p$ must be coprime, and then $$a^{p-1}\equiv 1\pmod p$$  and since $$1\cdot 1=1$$ any two powers returning $1$ as a remainder, can be multiplied or divided ( adding/subtracting their exponents) to form another power that returns $1$ , so if two coprime exponents were to both return $1$ you would end up with a cycle length of $1$ at some point. This is why cycle lengths divide the number of coprimes.
