Find the least positive integer $M$ such that $M^{77} \equiv 14 \pmod{31}$ 
Find the least positive integer $M$ such that $M^{77} \equiv 14 \pmod{31}.$

The way I have approached this question is by using Fermat's little theorem: 
$$a^{p-1} \equiv 1 \pmod p. $$
By trial and error -- I just started at $1$, then $2$, etc. -- eventually $M=18$ was the first integer (least positive) that gave the result congruent to $14$  mod $31$:
$$18^{30} \equiv 1 \pmod{31}.$$
$$ 18^{77} = 18^{2\cdot 30+17} \equiv 18^{17} \equiv 14 \pmod{31}.$$
This way of solving it is obviously quite long and tedious (especially without a calculator).  I am wondering if anybody can explain to me a more appropriate approach. 
 A: You're looking for $x$ so $x^{17}\equiv14\bmod31$. 
Since $30\times4-17\times7=1, (x^{17})^7\equiv x^{-1}\equiv 14^7$.  
$14\times20-9\times31=1$, so  $x\equiv {20}^7\equiv 5^7 2^{14}$.
$5^3\equiv1\bmod31, $ so $5^7\equiv 5\bmod 31$.
$2^5\equiv1\bmod 31, $ so $2^{14}\equiv 16\bmod 31$.
Therefore, $x\equiv 5\times16=80\equiv18\bmod 31$.
A: Well $31$ is prime so if $\gcd(31,M) \ne 1$ then $M^{77} \equiv 14 \pmod {31}$ will never happen.
So for any $M$ were $M^{77}\equiv 14$ then $M$ is relatively prime to $31$ and $M^{30}\equiv 1$ and $M^{77} \equiv M^{17}\equiv 14\pmod {31}$.
Now if we can do $17*k \equiv 1 \pmod {30}$ we can do $M^{17k}\equiv M \equiv 14^k\pmod {31}$.
And the rest is busy work....
And Euclid's Algorithm or other method [1] gives us $23*17\equiv 1 \pmod {30}$ so
$M \equiv 14^{23}$ which we can reduce. 
$2^5 \equiv 1 \pmod {31}$ and $7^3 \equiv 2\pmod {31}$
So $14^{23} \equiv 2^{23}*7^{23}\equiv 2^3*(7^3)^7*7^2\equiv 2^3*2^7*49\equiv 2^{10}*18\equiv 18\pmod{31}$
....
[1] Other method, in my case, is guessing.  $3*17 = 51$ and we need last digit $1$ and that can only be if we do $17*(3 + 10a)$ and there are only three chooses for $a$
A: There are special things about the number $31$ that can be leveraged to make a deterministic process without trial and error. It all hinges on how we can immediately see elements of orders $5$, $3$, and $2$ just from familiarity with small powers.


*

*$2^5\equiv1$, so $2$ is an element of order $5$ in the multiplicative group.

*$5^3=125=124+1\equiv1$, so $5$ is an element of order $3$ in the multiplicative group.

*Of course, $(-1)^2\equiv1$, so $-1$ is an element of order $2$ in the multiplicative group.


The multiplicative group is cyclic of order $30$, so isomorphic to $C_5\times C_3\times C_2$. And the observations above give an explicit isomorphism $C_5\times C_3\times C_2\to\mathbb{Z}_{31}^*$, where $(a^i,b^j,c^k)\mapsto 2^i5^j(-1)^k$. ($a$, $b$, and $c$ are generators for $C_5$, $C_3$, and $C_2$.)
Now consider the class of $14$, because we are looking for a way to write it as a product of $2$s, $5$s, and $(-1)$s: $\{14,45,76,107,138,169,200,\ldots\}$. That $200$ is nice, as it equals $2^3\cdot5^2$, a product of our generators. So $(a^3,b^2,e)\leftrightarrow14$ in the isomorphism. 
Now in $C_5\times C_3\times C_2$, what is the solution to $(x_a,x_b,x_c)^{17}=(a^3,b^2,e)$? We have three equations to solve that are much smaller and simpler than the original.


*

*$x_a^{17}=_5a^3\implies x_a^2=_5a^3\implies x_a^6=_5a^9\implies x_a=_5a^4$.

*$x_b^{17}=_3b^2\implies x_b^{2}=_3b^2\implies x_b^{4}=_3b^4\implies x_b=_3b$.

*$x_c^{17}=_2e\implies x_c=_2e$.


So the solution is $(a^4,b,e)$ which corresponds to $2^4\cdot5\cdot1=80\equiv18$.
