Solutions to $102^{70} -1 \equiv x^{37}$ mod $113$

I am trying to find integer solutions to the equation $$102^{70} -1 \equiv x^{37} \; (\mathrm{mod} \; 113)$$. I know $$112 = 37 \cdot 3 +1$$, so $$102^{70} - 1 \equiv x^{37} \; (\mathrm{mod} \; 113) \implies x(102^{70}-1)^3 \equiv (x^{37})^3 x \; (\mathrm{mod} \; 113)$$ $$\implies x(102^{70} - 1)^3 \equiv 1 \; (\mathrm{mod} \; 113)$$ So a particular solution is the multiplicative inverse of $$(102^{70} - 1)^3$$ in $$(\mathbb{Z}/113\mathbb{Z})^\times$$. I want to find the congruence of the inverse of $$102^{70} - 1$$ so that it lies between 0 and 112. Any one know how to do this? Also, how do I find other distinct solutions, if they exist?

• This conclusion is wrong$\implies x(102^{70} - 1)^3 \equiv 1 \; (\mathrm{mod} \; 113)$ since$x^(112) \not\equiv1 \; (\mathrm{mod} \; 113)$
– ole
May 17, 2020 at 22:14
• Isn't $x^{112} \equiv 1 \; (\mathrm{mod} \; 113)$ true by Fermat's Little Theorem, assuming $x \not \equiv 0 \; (\mathrm{mod} \; 113)$? May 17, 2020 at 23:23
• Well, successive squaring. It's not that hard. You'll $102^{70}\equiv ((-11)^2)^{35}\equiv 121^{35}\equiv 8^{35}\equiv.....$ something. May 17, 2020 at 23:25
• You are correct $(102^{70}-1)^3\equiv x^{111}$ so $(102^{70}-1)^3x \equiv x^{112} \equiv 1$. So you must find $[(102^{70}-1)^3]^{-1}$ which if there is any trick, don't see it but successive squaring is fairly straight forward. $(102^{70}-1)^3\equiv ((-11^{2*5*7}-1)^3$. Plenty of paths to explore.... May 17, 2020 at 23:30

This solution is a bit ad hoc, but oh well. First, let's compute $$102^{70}-1\bmod 113$$. $$102 \equiv (-11); (-11)^{70} \equiv (11^2)^{35}\equiv 8^{35}\equiv 2^{105}\equiv 2^{-7}\cdot 2^{112}\equiv 2^{-7}$$ $$2^7=128\equiv 15$$Note that $$15\cdot 15=225\equiv -1$$, so that $$15^{-1}=-15=98$$. Then $$102^{70}-1\equiv 97 \bmod 13$$. Now let's cube each side and multiply by $$x$$, as you suggested: $$x^{37}\equiv 97 \bmod 113$$ $$1\equiv x^{112}\equiv 97^3\cdot x\bmod 113$$ $$x\equiv (97)^{-3}\bmod 113$$Since $$7\cdot 16=112\equiv -1$$ and $$97\equiv -16$$, we have $$97^{-1}=7$$, so $$x\equiv (7)^{3}\bmod 113;\qquad x\equiv 4\bmod 113$$This solution is unique as well.

• Quick question, how do we know that that solution is the unique solution? May 17, 2020 at 23:35
• A general result: math.lsa.umich.edu/~lagarias/575chomework/… . In particular, $(37,112)=1$, so we get uniqueness. May 17, 2020 at 23:44
• Cool! good to know! Thanks May 17, 2020 at 23:44
• @isaortya See Taking modular k'th roots if unique May 18, 2020 at 0:13

$$102^{70}\equiv (-11)^{70} \equiv 11^{70}\equiv 121^{35}\equiv 8^{35}\equiv 2^{105}\equiv (2^7)^{15}\equiv 128^{15}\equiv 15^{15} \equiv (15^2)^7*15\equiv(225)^7*15\equiv (-1)^7*15 \equiv -15 \equiv 98 \pmod {113}$$

so we must solve $$x^{37}\equiv 97\equiv - 16 \pmod{113}$$

If $$x^{37}\equiv -16\pmod {113}$$ then

$$x^{111} \equiv(-16)^3 \equiv -2^{12}\equiv -2^{7}2^5\equiv -15*32\equiv -3*160\equiv -3*47\equiv -141 \equiv -28\equiv 85\pmod{113}$$.

Now $$113$$ is prime so be Fermat's Little Theorem $$x^{112}\equiv 1$$.

$$x*x^{111} \equiv 85x \pmod {113}$$

$$1 \equiv 85x\pmod {113}$$.

So we must solve $$85x + k113 = 1$$

$$85x + (85+28)k=1$$

$$85(x+k) + 28k = 1$$

$$(3*28 + 1)(x+k) + 28k = 1$$

$$(x+k) + 28(k+3(x+k)) = 1$$

If we let $$x+k =1$$ and $$k+3(x+k)= 3x+4k = 0$$ we will have a solution.

$$3x + 4k = 0$$ so $$x=\frac {-4k}{3}$$ so if we let $$k=-3$$ and $$x=4$$ we get $$85*4-113*3=1$$

So $$x \equiv 4\pmod {113}$$ is a solution.

• Lines $3$-$6$ are a special case of the general method of Taking modular $k$'th roots if unique, i.e. $\,x^{37} \equiv a\!\not\equiv\! 0 \pmod{\!113} \!\iff\! x \equiv a^{\large 1/37 \bmod 122} \equiv a^{\large \color{#c00}{-3}},\,$ by $\!\bmod 112\!:\, 1/37 \equiv 3/111 \equiv \color{#c00}{-3/1}\,$ by Gauss's algorithm. But the OP seems to already know how to take such roots. Also simpler is: $\!\bmod 113\!:\ 1/85 \equiv -1/{-}85\equiv 112/28\equiv 4.\,$ With such the solution is just a few lines. May 18, 2020 at 0:07