1
$\begingroup$

I'm trying to solve:

$$ x^{1477} \equiv 54 \mod 97 $$

Applying Euler-Fermat gives:

$$ x^{1477} = x^{15\cdot 96 + 37} = x^{37}\cdot x^{{96}^{15}} \equiv x^{37}\cdot 1^{15} = x^{37} \mod 97 $$

So instead of solving $ x^{1477} \equiv 54 \mod 97 $ one can solve $ x^{37} \equiv 54 \mod 97 $. How could I proceed from here? I know about the Chinese Remainer Theorem and Euler-Fermat.

$\endgroup$
  • $\begingroup$ try if $x=43$ fulfilles your equation $\endgroup$ – Dr. Sonnhard Graubner Feb 4 '18 at 16:45
  • 2
    $\begingroup$ @Dr.SonnhardGraubner Why would I come up with this? $\endgroup$ – user7802048 Feb 4 '18 at 16:50
  • $\begingroup$ i have used my TI calculator, TI-83 $\endgroup$ – Dr. Sonnhard Graubner Feb 4 '18 at 16:51
  • 1
    $\begingroup$ @Dr.SonnhardGraubner I'm not asking because for the actual solution. I want to understand how one might approach problems like this in general (even without using a calculator). $\endgroup$ – user7802048 Feb 4 '18 at 16:58
  • $\begingroup$ Where does the $x^{37}$ come from? $x^{1477}\equiv x^{1477\bmod96}=x^{22}\mod 97$. $\endgroup$ – Bernard Feb 4 '18 at 17:16
1
$\begingroup$

If $x^{37} \equiv 54 \pmod {97}$ then $x^{37\cdot 24} \equiv 54^{24} \equiv 1 \pmod {97}$ because the order of $54 \pmod {97}$ is $24$.

This means the order of $x$ is a common divisor of $96$ and $37 \cdot 24$.

Therefore the order of $x$ is a divisor of $24$, and so $x^{24} \equiv 1 \pmod {97}$.

But if $k$ is a divisor of $24$ then $x^k \equiv 1 \pmod {97}$ implies $1 \equiv x^{37k} \equiv 54^k \pmod {97}$ so $24$ divides $k$.

Therefore the order of $x$ is $24$.

That means $x^{12} \equiv -1 \pmod {97}$.

So $54 \equiv x^{37} \equiv x^{1 + 3\cdot 12} \equiv x\left(x^{12}\right)^3\equiv x(-1)^3 \equiv -x \pmod {97}$

Finally, we obtain $x \equiv -54 \pmod {97}$, or $x \equiv 43$.

$\endgroup$
  • $\begingroup$ Neat solution. Thank you! $\endgroup$ – user7802048 Feb 4 '18 at 17:04
  • $\begingroup$ Is there a quicker way to find the order of $54$ other than trying all the divisors of $96$ in increasing order? $\endgroup$ – user7802048 Feb 4 '18 at 21:12
  • $\begingroup$ In decreasing order. To find the order of $x$, test $x^{48}$ and $x^{32}$. If neither is $1$, then $x$ is primitive. In our case, $x^{48}=1$ but $x^{32}\ne1$, so that $x$ is a square but not a cube. Now try $x^{24}$, equal to $1$ in our case, it’s a fourth power but not a cube. Done. $\endgroup$ – Lubin Feb 4 '18 at 22:06
0
$\begingroup$

Let us find integers $a,b$ such that $37a+96b=1$

Like Solving a Linear Congruence,

$$37\cdot13-96\cdot5=1$$

$$x^{37}\equiv54\pmod{97}$$

$$x=x^{37\cdot13-96\cdot5}\equiv54^{13}$$

Now by observation $2^{10}\equiv54\pmod{97},2^{11}\equiv11$

$$54^{13}\equiv(2^{10})^{13}\equiv2^{130}\equiv2^{34}\equiv2(11)^3=?$$

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