One problem with Euler's function 
Let $n=100$. Is $\phi(n)$ the smallest number $\lambda$ such that if $\gcd(a,n)=1$ then $a^{\lambda}\equiv_{n}1$ ? Generalize this observation.

I suppose the answer is no. I've read something about $\mathrm{ord}_n(a)$ but group theory rather goes beyond my discrete mathematics course. I don't know what exactly author of this task had on mind, but maybe what is the simplest way to find such smallest $\lambda$?
 A: 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$.
A: Write $n=100 = 4 \cdot 25$. By Fermat–Euler, we have


*

*$a^{2}\equiv 1 \bmod 4$ when $(a,4)=1$ because $\phi(4)=2$

*$a^{20}\equiv 1 \bmod 25$ when $(a,25)=1$ because $\phi(25)=20$


We conclude that $a^{20}\equiv 1 \bmod 100$ when $(a,100)=1$.  Note that $20<40 = \phi(100)$.
So $\lambda$ divides $20$. You now need to argue that $\lambda=20$ or find a smaller exponent.
