# How to solve $\ x^{12}\equiv 87\pmod{101}$

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

• 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).
– lulu
Mar 3, 2019 at 15:13
• 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.
– lulu
Mar 3, 2019 at 15:14
• @lulu "Only a few seconds including the time for programming" - Somewhat exaggerated, but I agree to both comments. Mar 3, 2019 at 15:57
• @Peter "Solve x^12=87 mod 101" is all it take in WA
– lulu
Mar 3, 2019 at 16:06
• @Peter there's Tonelli-Shanks for primes. Not even close to worth it here. For composite moduli the problem is equivalent to factorization.
– lulu
Mar 3, 2019 at 16:25

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

Algorithmically let's use Shanks' baby giant step. The Remark below shows $$2$$ is a primitive root $$({\rm ord}\,2 = 100)$$ so $$\,87 \equiv 2^{\large n}\,$$ is solvable, e.g. by baby-giant step, i.e. we solve $$\,87\cdot 2^{\large 10j}\equiv 2^{\large k}\,$$ for $$\,0\le j,k < 10 = \lceil\sqrt{100}\rceil,\,$$ by repeatedly mutliplying $$\,87\,$$ by $$\,2^{\large 10}\! \equiv 1010\!+\!14\equiv 14\,$$ until we reach some $$\,2^{\large k}.\,$$ It requires $$\,\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$$

• See here for another worked example. Nov 21, 2019 at 6:25

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

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