Find the number of solutions of $x^k\equiv 45\pmod{97}$

Question

Let $5$ be a primitive root of $97$ and $\text{ind}_5 (45)=45$ find the number of solutions of $x^k\equiv 45\pmod{97}$ where $k=7,8,9$

My attempt:

$$5^{45}\equiv 45 \pmod{97}$$

For $k=7:$

$$x^7\equiv 45\pmod{97}$$

$$\text{ind}_5x^7=7\cdot\text{ind}_5x\equiv45 \pmod{\phi(97)}$$

$$7\cdot\text{ind}_5x\equiv45 \pmod{96}$$

$$\text{ind}_5x\equiv75 \pmod{96}$$

I am stuck here

Answer 1

For a given integers $a,b,m$ let $d=\gcd(a,m)$. Generally, the number of solutions of $ax\equiv b(\text{mod}\,m)$ is $0$ if $d\nmid b$ or $d$ if $d\mid b$.

In your case, the congruence is equivalent to the following linear congruence: $$ k\cdot\text{ind}_5x\equiv 45(\text{mod}\,96) $$ Hence, the number of solutions is $\gcd(k,96)$ if $\gcd(k,96)\mid 45$ or $0$ if $\gcd(k,96)\nmid 45$.

Answer 2

If $G$ is a cyclic group of order $n$, then the map $x \mapsto x^k$ is $d$-to-$1$, where $d=\gcd(k,n)$ because its kernel has order $d$. In other words, if $x^k=g$ has a solution, then it has $d$ solutions.

In your case, $G=U(97)$ and $n=\phi(97)=96$. So

• exactly $1$ solution for $k=7$.

• at most $8$ solutions for $k=8$.

• at most $3$ solutions for $k=9$.

The index calculus you mention works for deciding whether there are any solutions.

• $7 j \equiv 45 \bmod 96$ has a solution because $\gcd(7,96)=1$ divides $45$.

• $8 j \equiv 45 \bmod 96$ does not have a solution because $\gcd(8,96)=8$ does not divide $45$.

• $9 j \equiv 45 \bmod 96$ has a solution because $\gcd(9,96)=3$ divides $45$.

You have found the solution $j=75$ for $k=7$ and so $x=5^{75} \equiv 63 \bmod 97$.

For $k=9$, you need to solve $3 j \equiv 15 \bmod 32$, which gives $j \equiv 5 \bmod 32$.