3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can u please explain in the last Lagrange part , why d|6? $\endgroup$ – Akash Banerjee May 23 '17 at 9:05
  • $\begingroup$ 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$. $\endgroup$ – CL. May 23 '17 at 10:38
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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