# Solving $2^x \equiv x \pmod {11}$

Solve $2^x \equiv x \pmod {11}$.

I know 2 is a primitive root modulo 11.

So. I get $x \equiv \operatorname{ind}_2x \pmod {10}$

And I'm stuck!

(Maybe I can $x=1$, $x=2$, $x=3$, and so on... but looking for brilliant method.)

Could you give me some advice?

Is 'primitive root' useful thing for solving this type?

 P.S.

And I'd like to check this via http://wolframalpha.com

but this show.... http://www.wolframalpha.com/input/?i=2%5Ex++mod11+%3Dx

I wanna know proper command for check this problem.

maybe not [ 2^x mod11 =x ]

• I suggest trial and error – Hagen von Eitzen Nov 28 '14 at 7:39
• @HagenvonEitzen Thank you for your comment. And you mean substitution for x? – user143993 Nov 28 '14 at 7:41
• I think you mean $x\equiv \text{ind}_2(x)$? – David Peterson Nov 28 '14 at 7:43
• @DavidPeterson Really thank you. I edited :-) – user143993 Nov 28 '14 at 7:48
• Wolfram – Quang Hoang Nov 28 '14 at 8:02

Using Fermats little theorem, it follows that $2^x\equiv2^{x \mod 10}$. This should be equal to $x\mod11$. The residue classes are from $x\equiv0$ to $x\equiv9$: $$1;2;4;8;5;10;9;7;3;6;$$

This should be equal to the residue class $x\mod11$. Using the Chinese remainder theorem: \begin{align} x\equiv0\mod 10\qquad &x\equiv1&\mod11\implies &x\equiv100&\mod110\\ x\equiv1\mod 10\qquad &x\equiv2&\mod11\implies &x\equiv101&\mod110\\ x\equiv2\mod 10\qquad &x\equiv4&\mod11\implies &x\equiv92&\mod110\\ x\equiv3\mod 10\qquad &x\equiv8&\mod11\implies &x\equiv63&\mod110\\ x\equiv4\mod 10\qquad &x\equiv5&\mod11\implies &x\equiv104&\mod110\\ x\equiv5\mod 10\qquad &x\equiv10&\mod11\implies &x\equiv65&\mod110\\ x\equiv6\mod 10\qquad &x\equiv9&\mod11\implies &x\equiv86&\mod110\\ x\equiv7\mod 10\qquad &x\equiv7&\mod11\implies &x\equiv7&\mod110\\ x\equiv8\mod 10\qquad &x\equiv3&\mod11\implies &x\equiv58&\mod110\\ x\equiv9\mod 10\qquad &x\equiv6&\mod11\implies &x\equiv39&\mod110\\ \end{align}

The given residue classes $\mod110$ are the answer to the question.

• I think everyone else who looked at this question assumed it would only depend on $x$ modulo 11, including myself. Great work! – RghtHndSd Nov 28 '14 at 16:45
• Don't you mean mod $110$ instead of $121$? – Barry Cipra Nov 28 '14 at 17:03
• Yes, thanks for pointing this out, @Greg thanks for editing. – Thijs Nov 28 '14 at 17:45
• Wow.. Really great!! wow....... wow.. both modulo 10 and 11...!!! Thank you for your answer – user143993 Nov 30 '14 at 2:54

Let $a$ be any nonnegative integer and let $k=a-2^a$. Let $x=a+10k$. Then, using a mixture of unconditional equality and mod-$11$ congruence, we have

$$2^x=2^{a+10k}\equiv2^a=a-(a-2^a)=a-k\equiv a+10k=x$$

This doesn't give every solution, but it does give an infinite family of solutions (all negative). For example, $a=1$ gives $2^{-9}\equiv-9$ mod $11$.

Added later: In light of Thijs's complete solution, it's worth noting that the explicit formula here, which can be written as

$$x=11a-10\cdot2^a$$

gives, for $a=0,1,2,\ldots,9$, the values $-10,-9,-18,\ldots,-5021$, which agree mod $110$ with the residues in Thijs's Chinese remainder theorem results, in the exact same order, i.e., $-10\equiv100$, $-9\equiv101$, $-18\equiv92,\ldots,-5021\equiv39$ mod $110$. Presumably this generalizes in some fashion to something like

$$x\equiv q^x\text{ mod } p\iff x\equiv pa-(p-1)q^a\text{ mod }p(p-1)\text{ for some }a\in\mathbb{N}$$

This is Mathematica code. I believe that it will work on Wolfram Alpha.

m = 11;
Select[Range[m], Mod[2^#, m] == # &]
{7}


For large values of $m$ this will be faster

m = 1234567;
Select[Range[m], PowerMod[2, #, m] == # &]
{313692}


m = 11;

• I acknowledge it is quite cryptical. Range[m] is $\{1,\dots,m\}$. Mod[2^a,b]=PowerMod[2,a,b] computes $2^a\mod b$. The #, & construction is a pure function. # is the argument. It returns True if the equality holds, False if not. Select selects the values in Range[m] returning True. – Julián Aguirre Nov 28 '14 at 16:16