1
$\begingroup$

Can someone help me to solve the following congruent equation. I have tried to use Fermat's little theorem but failed to solve this: $x^{12}=87(\mod 101)$

$\endgroup$
  • $\begingroup$ What's wrong with brute force? It only takes a few seconds with a machine (including the programming time. The actual computation is effectively instantaneous). $\endgroup$ – lulu Mar 3 at 15:13
  • $\begingroup$ General note: these problems tend to be really hard, computationally. Brute force is an excellent approach, for numbers as small as these. You could, of course, find a primitive root and work from there, but that's a lot more computation. $\endgroup$ – lulu Mar 3 at 15:14
  • 1
    $\begingroup$ @lulu "Only a few seconds including the time for programming" - Somewhat exaggerated, but I agree to both comments. $\endgroup$ – Peter Mar 3 at 15:57
  • $\begingroup$ @Peter "Solve x^12=87 mod 101" is all it take in WA $\endgroup$ – lulu Mar 3 at 16:06
  • 1
    $\begingroup$ @Peter there's Tonelli-Shanks for primes. Not even close to worth it here. For composite moduli the problem is equivalent to factorization. $\endgroup$ – lulu Mar 3 at 16:25
1
$\begingroup$

Let us try to use Fermat's little theorem

We know $$x^{108}=(x^{12})^9\equiv 87^9\equiv 36\mod 101$$ implying $$x^8\equiv 36\mod 101$$

This gives us $$x^{104}=(x^8)^{13}\equiv 36^{13}\equiv 95\mod 101$$

implying $$x^4\equiv 95\mod 101$$ Not sure whether we can simplify even further.

The integer square roots of $95$ modulo $101$ are $14$ and $87$, the square roots of $14$ modulo $101$ are $32$ and $69$ (two solutions) and the square roots of $87$ modulo $101$ are $17$ and $84$ (the two other solutions).

$\endgroup$
1
$\begingroup$

Algorithmically let's use Shanks' baby giant step. We hope $2$ is a primitive root $({\rm ord}\,2 = 100)$ and we use this method to write $87 \equiv 2^{\large n},\,$ i.e. we seek $\,87\cdot 2^{\large 10j}\equiv 2^{\large k}\,$ for $\,0\le j,k < 10,\,$ by repeatedly mutliplying $\,87\,$ by $\,2^{\large 10}\! \equiv 1010\!+\!14\equiv 14\,$ till we reach some $\,2^{\large k}.\,$ It takes $\,\color{#c00}4\,$ multiplications, i.e.

$$87\equiv-14 \overset{\large \times\color{#c00}{14}}\to 6\overset{\large\times\color{#c00}{14}}\to -17\overset{\large\times\color{#c00}{14}}\to -36\overset{\large\times\color{#c00}{14}}\to 1 $$

so $\ \smash[t]{87(\overbrace{2^{\large 10}}^{\large \color{#c00}{14}})^{\Large\color{#c00}4}}\equiv 1\overset{\large \times\, 2^{\LARGE 60}\!}\Longrightarrow 87\equiv 2^{\large 60}\!\equiv 2^{\large 12x}\!\!\!\iff$ $\! 12x\equiv 60\pmod{\!100}\!\iff\! n\equiv 5\pmod{\!25}$

Hence the solutions are $\,x\equiv 2^{\large 5}\!\equiv 32,\,\ x\equiv 2^{\large 30}\!\equiv 14^{\large 3}\!\equiv 17\,$ and their negatives $(\times\, 2^{\large 50}\!\equiv -1)$

Remark $ $ We skipped an optimization in order to better show the general method. Namely, at the start we already have $\,87\equiv -14\equiv -2^{\large 10}\equiv 2^{\large 60}\,$ by $\,-1\equiv 2^{\large 50},\,$ by $\,{\rm ord}\,2 = 100.\,$

To prove $\,{\rm ord}\,2 = 100,\,$ by the Order Test it suffices to show that $\,2^{\large 100/p}\!\not\equiv 1$ for all primes $\,p\mid 100,\,$ i.e. $\,2^{\large 20}\!\not\equiv 1,\, $ $2^{\large 50}\!\not\equiv 1.\,$ That's easy: $\,2^{\large 20}\!\equiv 14^{\large 2}\!\equiv 196\equiv -6,\,$ so $\,2^{\large 50}\!\equiv 14(-6)^{\large 2}\!\equiv 17(-6)\equiv -1$

$\endgroup$
0
$\begingroup$

Numbers congruent to $87 \pmod {101}$ are $87,\; 87+101=188,\; 87+2\times 101=\color{red}{289}, ...$

and $87-101=-14,\;87-2\times 101=-115,\;87-3\times 101=\color{blue}{-216},...$

Note that therefore $17^2=289 \equiv87\pmod{101}$ and $(-6)^3=-216 \equiv 87 \pmod{101}.$

Furthermore $17\times6=102 \equiv 1 \pmod{101}.$

Therefore $17^5\equiv17^2/6^3\equiv -1 \pmod{101}.$

Thus $17^{12}=17^{10}\times17^2=(17^5)^2\times17^2\equiv87 \pmod {101},$

so $x=17$ is a solution to $x^{12}\equiv87\pmod{101}$.

$\endgroup$
  • $\begingroup$ I realize I found a solution but not all solutions. $\endgroup$ – J. W. Tanner Mar 3 at 16:15
  • $\begingroup$ The solutions are $\pm17,\,\pm 32$, easily computable by baby-giant step - see my answer. $\endgroup$ – Bill Dubuque Mar 3 at 18:41

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.