Determine the number of incongruent solutions of:
(a) $x^3 ≡ 2 \pmod {29}$
(b) $x^{16} ≡ 25 \pmod {29}$
We will be using Proposition (6.17). Let $n$ have a primitive root and $a$ and $n$ be relatively prime. The congruence $x^m \equiv a \pmod n$ has a solution if and only if $a^{\phi(n)/g} \equiv 1 \pmod n$ where $g = \gcd (m, \phi (n))$. Additionally, there are exactly $g$ incongruent solutions.
(a) Since $\gcd(29,2)=1$ we can use Proposition (6.17). Noting that $\gcd(3, \phi(29))=1$, and by Euler's Theorem $2^{28} \equiv 1 \pmod {29}$, we have
$$ 2^{\frac{\phi(29)}{\gcd(3, \phi(29))}} \equiv 2^{\frac{28}{1}} \equiv 2^{28} \equiv 1 \pmod {29}$$
And so the congruence has solutions, and in fact has 1 unique incongruent solution modulo 29.
(b) Since $\gcd(29,25)=1$ we can use Proposition (6.17). Noting that $\gcd(16,28)=4$, we have
$$ 25^{\frac{\phi(29)}{\gcd(16, \phi(29))}} \equiv 25^{\frac{28}{4}} \equiv (-4)^{7} \equiv -16384 \equiv 1 \pmod {29}$$
And so the congruence has solutions, and there are 4 unique incongruent solutions modulo 29.