computing $29^{25}$ (mod 11)

3.3k Views Asked by At

I'm trying to learn how to use Fermat's Little Theorem.

$29=2\cdot11+7 \Rightarrow 11\nmid29$

by the theorem we have $29^{10}\equiv 1$(mod 11)

$25=10\cdot 2 + 5$

$ 29^{25}=(29^{10})^2\cdot29^5\equiv 29^5$(mod 11)

where do I go from here?

1

There are 1 best solutions below

0
On

$$29^{25}\equiv(-4)^{25}\equiv(-4)^{-5}\equiv(-3)^{5}\equiv-27\cdot9\equiv(-5)(-2)\equiv10\quad(\text{mod }11)$$ I use the theorem in the second step and the third step works because $3\cdot4\equiv1\ (\text{mod }11)$.