Use the fact that $2$ is a primitive root modulo $101$ to find all solutions to $x^7\equiv-2\pmod{101}$

Question

Use the fact that $2$ is a primitive root modulo $101$ to find all solutions to $$x^7\equiv-2\pmod{101}.$$

My number theory book says to compare powers of $2$ to $101$ to express $-2$ as a power of $2$ modulo $101$. I have computed powers of $2$ up to $40$ where my calculator loses accuracy so I have to assume there is some trick that I'm missing. I have read all through this chapter but I cannot find it for the life of me.

Answer 1

Justify the following steps. All the arithmetic done in the group $\Bbb{Z}_{101}^*$ that is now given to be cyclic of order $100$ with generator $2$:

1. Because $-1$ is the only element of order two we must have $2^{50}\equiv-1$.
2. Therefore $2^{51}\equiv -2$.
3. Therefore $x=2^t$ is a solution of $x^7\equiv-2$ if and only if $2^{7t}\equiv 2^{51}\pmod{101}$ if and only if $$7t\equiv 51\pmod{100}.$$

Because $7$ is coprime to $100$ there will be a unique residue class modulo $100$ of acceptable value of $t$. I trust you have studied linear congruences earlier, and solving for $t$ poses no problem to you. Then you just need to calculate $x=2^t$.

Answer 2

Using discrete logarithm

$7$ind$_2x\equiv 1+\dfrac{\phi(101)}2\pmod{100}\equiv51\equiv-49$

$\implies$ind$_2x\equiv-7\pmod{100}\equiv93$ as $(7,100)=1$

$\implies x\equiv2^{93}\pmod{101}$