Find the least value of $n$ such that $n^{25}\equiv_{83}37$

Question

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?

Answer 1

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.

Answer 2

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.