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

• 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. – fleablood Jan 5 '20 at 18:26

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

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

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