3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Well you should have gotten that $M^{77} \equiv M^{17}$ for all $M$ not a multiple of $31$. So if $M^{17}\equiv 14$ then $M^{34}\equiv M^4\equiv 14^2\equiv 10\pmod{31}$ and... look for insight. $\endgroup$ – fleablood Jan 5 '20 at 18:26
1
$\begingroup$

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$

$\endgroup$
2
$\begingroup$

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

$\endgroup$
0
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.