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

4 Answers 4

2
$\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$
2
  • $\begingroup$ Can u please explain in the last Lagrange part , why d|6? $\endgroup$ May 23, 2017 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$
    – Bryan Shih
    May 23, 2017 at 10:38
1
$\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$
1
$\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$
1
$\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$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .