Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
If this is homework, tag it as such. –  lhf Aug 16 '12 at 12:29
2  
It's not a homework, I've got summer break. I just want to learn sth. –  ray Aug 16 '12 at 13:05

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
    
We don't really need to to iterate all divisors of $\phi(n)$. –  lhf Aug 16 '12 at 12:32
    
That $\text{ord}_{100}(a)$ is a proper divisor of $40$ is not adequate grounds to conclude that $\text{ord}_{100}(a) \mid 20$ (even though it is true by @lhf's correct answer). –  Erick Wong Aug 16 '12 at 14:03
    
I think in that approach , 8(∤20) can be $ord_{100}a$ –  lab bhattacharjee Aug 16 '12 at 16:27

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.