Multiplicative order of elements of $Z_n$

Question

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.

Answer 1

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.