Find the number of solutions of $x^k\equiv 45\pmod{97}$ 
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
 A: 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$.
A: 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$. 
