Find all solutions to $x^9 \equiv 25 \pmod {29}$
- I referred to a table of indices in the back of my book for help but am still a bit confused, any help/hints are greatly appreciated.
2 Answers
$\begingroup$Raise to the power of 25 and then use Fermat's little theorem.
Why to 25? Because 9.25 - 1 is divisible by 28 which is $\phi(29)$.
Here are the details. The congruence:
(1) $y^{9}\equiv 25 \mod{29}$
implies that:
(2) $(y^{9})^{25} = y^{9.25} = y^{225} \equiv 25^{25} \equiv 24 \mod{29}$
But $225$ gives remainder $1$ when divided by $\phi(29)=28$.
So:
(3) $y^{225} \equiv y^{224} . y \equiv 1 . y \equiv y \mod{29}$
(since $28$ divides $224$)
Now from (3) and (2) we get:
(4) $y^{225} \equiv y \equiv 24 \mod{29}$
which is the solution you were looking for.
How did I know to raise $y^{9}$ to the power of $25$ as I did in (2)?
Well, I first looked for a natural number $k$ such that: $9.k = 28.t+1$ for some natural $t$.
The smallest such $k$ happens to be $k=25$.
If (k,$\phi(m)$)=1 and $(b,m)=1$, writing $ku-\phi(m)v=1$ (you can do this using the extended euclidean algorithm), one can show that $x=b^u$ is a solution to $x^k\equiv b \pmod m$. The numbers are small enough in this problem that brute force is probably just as good, but this method is useful so it is good to know.
In this particular case, one can write $9(25)-28(8)=1$, so we can see that $u=25$, so $x=25^{25}$ is a solution. Using a method such as successive squaring, we see that $x \equiv 24 \pmod {29}$.
$\endgroup$
