Let λ be the smallest positive number such that $a^λ \equiv 1 \pmod n$ where (a,n)=1.
By Euler's totient theorem, $a^{\phi(n)}\equiv 1 \pmod n$
Let $\phi(n)=rλ+s$ where 0 ≤s<λ
So,$1≡a^{\phi(n)}=a^{rλ+s}=(a^λ)^r\cdot a^s≡a^s$
So, there comes another s<λ, $a^s≡1 \pmod n$, which is impossible as λ is the smallest=>s=0.
=> $λ| \phi(n)$
Unfortunately, we need to iterate the divisors of $\phi(n)$ to find the smallest positive λ which is called $\mathrm{ord}_na$.
We know, n has a primitive root if it is of the form $2, 4, p^a , or 2p^a,$ where p is an odd prime and integer a≥0.
So, we don't need to traverse up to $\phi(n)$ if n is not of any the above form.
For example, $\phi(100)=40$. As 100=4*25, it can not have a primitive root, no $a$ co-prime to 100 can have order 40,$ ord_{100}a$ must be one of $1,2,4,5,8,10,20$.
According to Carmichael Function, we can off-course, make reduction of the traversal. The reduction will increase with the number of unique prime divisors.
Using Carmichael Function, $ord_{100}a$ must divide lcm$(\phi(4)\cdot \phi(25))=lcm(2,20)=20$.