Find the least value of $n$ such that $n^{25}\equiv_{83}37$ Let $n\in\mathbb{N}$. Find the least value of $n$ such that $n^{25}\equiv_{83}37$.
I concluded that $0<n<83$. Then I wrote $n^{25}$ as $\left(n^5\right)^5$ and let $t=n^5$. Now, it is hard to solve $t^5\equiv_{83}37$. How to solve this?
 A: We describe a somewhat general procedure, which works for solving $x^k\equiv a\pmod{p}$, when $k$ and $p-1$ are relatively prime. It is overkill for our problem.
Using the Extended Euclidean algorithm, or otherwise, note that $25a\equiv 1\pmod{82}$, where $a=23$. So we have found the modular inverse of $25$ modulo $82$. So $25a=82b+1$, where $b$ happens to be $7$.
It follows that 
$$(37^{23})^{25}\equiv (37^b)^{82}\cdot 37^1\equiv 37\pmod{83}.$$
Thus an answer to the problem, but of very much the wrong size, is $37^{23}$.  We want to find the remainder when this is divided by $83$. 
Use modular exponentiation, preferably an efficient form such as the Binary Method. 
A: Working mod $83$, a prime number. Fermat's little theorem says:
$$a^{83} \equiv a$$ for any integer $a$ so 
$$a^{m \cdot 82+1} \equiv a$$ for any $a$ and $m\ge 0$ integers
so in particular
$$37^{m \cdot 82+1} \equiv 37$$
Now try to find $m$ so that $m\cdot 82 + 1 = k \cdot 25$ thus getting $37^{m \cdot 82+1}= (37^k )^{25}$.  By trial and error or using the GCD algorithm we get the smallest such positive $m=7$ 
$$7\cdot 82 + 1 = 575 = 576-1 = 24^2-1 = 23 \cdot 25$$
with the corresponding $k=23$.
Therefore 
$$(37^{23})^{25}\equiv_{83} 37$$
so now we are left with calculating $37^{23}$ mod $83$. Instead of raising $37$ to the power $23$ and determining its remainder mod $83$ it is simpler to obtain $37^{23}$ mod $83$ using the properties of modular multiplication. 
Note that 
$$23 = 16 + 4 + 2 + 1 = 2^4 + 2^2 + 2^1 + 2^0$$
and so 
$$37^{23} \equiv 37^{2^4} \cdot 37^{2^2}\cdot 37^2 \cdot 37$$
Note the rule $37^{2^n} = (37^{2^{n-1}} )^2$. Therefore:
\begin{eqnarray*}
37^1 &\equiv & 37\\
37^2  &\equiv &  41\\
37^4 &\equiv &  41^2 \equiv  21\\
37^8  &\equiv & 21^2\equiv 26\\
37^{16}  &\equiv &  26^2 \equiv 12
\end{eqnarray*}
and so 
$$37^{23} \equiv 12\cdot 21\cdot 41 \cdot 37 \equiv 69$$
We get 
$$69^{25} \equiv_{83} 37$$
The solution $69$ is the unique one mod $83$ and thus $n=69$ is the smallest solution.
