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

Question

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.

Answer 1

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$

Answer 2

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

Answer 3

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