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

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.

• Can u please explain in the last Lagrange part , why d|6? – Akash Banerjee May 23 '17 at 9:05
• Actually, it is a typo, I have edited. $d$ is order of element $5$, and we know the order divides any $n$ such that $5^n=1 \pmod 9$. – Cy L Shih May 23 '17 at 10:38

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

1. 5$^n$ ≡ 1 (mod9)
2. 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.

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.