0
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ This conclusion is wrong$\implies x(102^{70} - 1)^3 \equiv 1 \; (\mathrm{mod} \; 113)$ since$x^(112) \not\equiv1 \; (\mathrm{mod} \; 113) $ $\endgroup$
    – ole
    May 17, 2020 at 22:14
  • $\begingroup$ Isn't $x^{112} \equiv 1 \; (\mathrm{mod} \; 113)$ true by Fermat's Little Theorem, assuming $x \not \equiv 0 \; (\mathrm{mod} \; 113)$? $\endgroup$
    – isaortya
    May 17, 2020 at 23:23
  • 1
    $\begingroup$ Well, successive squaring. It's not that hard. You'll $102^{70}\equiv ((-11)^2)^{35}\equiv 121^{35}\equiv 8^{35}\equiv..... $ something. $\endgroup$
    – fleablood
    May 17, 2020 at 23:25
  • $\begingroup$ 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.... $\endgroup$
    – fleablood
    May 17, 2020 at 23:30

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
4
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ May 18, 2020 at 0:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .