least positive integer n such that $5^n\equiv 1 \pmod{36}$ what is the least positive integer n such that $5^n\equiv 1 \pmod{36}$ ?
By computation I had found that $n=6$.
But is there any other method? Because computation is too much time consuming.I tried to google it, and find something similar , which is #Carmichael function .
But I cant really understand what it is actually.And how can it help me. 
so please help. Thanks.
 A: Intuitively, it is best to understand the bijective nature of unit groups, if $p,q$ are coprime, there is a bijection,$$(\mathbb{Z}/pq\mathbb{Z})^{\times} \rightarrow (\mathbb{Z}/ p \mathbb{Z})^ \times \times  (\mathbb{Z}/q\mathbb{Z}) ^\times$$
given by $\bar{m}_{pq} \leftrightarrow (\bar{m}_p, \bar{m}_q )$. where $\bar{m}_n$ denotes the equivalance class of $m$ modulo $n$. 

In our case, it is easy to derive the following equivalence, 
$$5^n =1 \pmod {36} \Leftrightarrow 5^n = 1 \pmod 9, \, 5^n =1 \pmod 4$$
By Euler Totient, $5^6=1 \pmod 9$, and clearly $5^1 =1 \pmod 4 \Rightarrow 5^6=1 \pmod 4$. So we know at worst $n=6$. 
Also, the order $d$ of $5$ satisfies $d|6$ by Euclidean Algorithm. So all we had to do is test if $5^d =1 \pmod 9$ for $d=1,2,3$ which is easy. 
A: We can solve this using the Euler totient function.
Principle: a$^{Φ(m)}$≡1(mod m) where gcd(a,m)=1
Now We Can deduce from your given equation a few things from 5$^n$ ≡ 1 (mod36)
.


*

*5$^n$ ≡ 1 (mod9)

*5$^n$ ≡ 1 (mod4)


Now let's apply a$^Φ(m)$≡1(mod m)
5$^{Φ(9)}$≡1(mod 9) ⇔ 5$^6$≡1(mod 9)
5$^{Φ(9)}$≡1(mod 4) ⇔ 5$^2$≡1(mod 9) ⇔ 5$^6$≡1(mod 9)
Therefore n=6.
A: The Euler totient of $36$ is $12$ so $n|12$.  We can't have $n $ odd as then $5^n \equiv -1 \bmod 3$.  As $5^2 \equiv 7 \bmod 9$ this must be cubed to give residue  $1 \bmod 9$ meaning $n \ge 6$.  But then $5^6\equiv 1 \bmod 9$ and also $5^6\equiv 1^6\equiv 1 \bmod 4$ so $n=6$ exactly.
A: A more elementary calculation:  The binomial theorem gives us 
$$5^n \equiv (6-1)^n \equiv 6^n -\binom{n}{1}6^{n-1} +\cdots $\binom{n}{n-1}6(-1)^{n-1} + (-1)^n \equiv n(6)(-1)^{n-1}+(-1)^n  \equiv 1 \pmod{36}. $$
Since the right side is one more than a multiple of $6$, so is the left side which means $n$ is even.  So we have
$$-6n +1 \equiv 1 \pmod{36} \implies 6n\equiv 0 \pmod{36} \implies n\equiv 0 \pmod{6}. $$
So the smallest positive such $n$ is $6$.
