One problem with Euler's function

Question

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$?

Answer 1

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$.

Answer 2

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.