Multiplicative order of elements of $Z_n$ So I was wondering how to find the order of elements under multiplication in $Z_n$. When $n$ is prime the problem is simpler since we know that then all the non-zero elements are units, and $|U(p)|=p-1$ so their order must divide $p-1$. This is some sort of clue, but when $n$ is not prime I have no idea how to tackle this problem and would appreciate the help.

There are two generalizations of Fermat's theorem for composite modulus. They help reduce the number of possible candidates for multiplicative orders.
Euler's theorem:

$a^{\varphi (n)} \equiv 1 \bmod{n}$ when $\gcd(a,n)=1$

This is Lagrange's theorem for the group of units $U(n)$, which has order $\varphi (n)$.
Carmichael's theorem:

$a^{\lambda (n)} \equiv 1 \bmod{n}$ when $\gcd(a,n)=1$

Here, Carmichael's function $\lambda (n)$ gives the exponent of $U(n)$. Naturally, $\lambda (n)$ divides $\varphi (n)$, but it is usually much smaller than $\varphi (n)$ when $n$ has several prime factors.
