1. ## another mod

71^71 is congruent to x(mod 17)

2. Hello,
use Euler's generalization of Fermat's Little Theorem : if and only if $\displaystyle gcd(a, m) = 1$, $\displaystyle a^{\varphi{(m)}} \equiv 1 \pmod{m}$, where $\displaystyle \varphi{(m)}$ is the Euler totient of $\displaystyle m$.

In your case, $\displaystyle 17$ is a prime number (lucky you), so $\displaystyle \varphi{(17)} = 17 - 1 = 16$. And $\displaystyle gcd(71, 17) = 1$. Therefore, $\displaystyle 71^{16} \equiv 1 \pmod{17}$. Good.

Now note that $\displaystyle 71^{71} \equiv (71^{16})^4 \times 71^7 \pmod{17}$. Plug in the result you found with Euler's generalization, you find that :

$\displaystyle 71^{71} \equiv 1^4 \times 71^7 \equiv 71^7 \pmod{17}$.

$\displaystyle 71^7$ still is a big number, so we are going to break it into pieces. You can thus write the following :

$\displaystyle 71^{71} \equiv 71^7 \equiv (71^2)^3 \times 71^1 \pmod{17}$.

You can easily compute $\displaystyle 71^2 \equiv 5041 \equiv 9 \pmod{17}$, so :

$\displaystyle (71^2)^3 \times 71 \equiv 9^3 \times 71 \pmod{17}$

$\displaystyle 9^3$ is not too big and can be computed quickly (if not, break it into two pieces), so $\displaystyle 9^3 \equiv 729 \equiv 15 \pmod{17}$. While we're at it, $\displaystyle 71 \equiv 3 \pmod{17}$. We get :

$\displaystyle 9^3 \times 71 \equiv 15 \times 3 \equiv 45 \equiv 11 \pmod{17}$.

And we are done ! We can now write :

$\displaystyle 71^{71} \equiv 71^7 \equiv (71^2)^3 \times 71^1 \equiv 11 \pmod{17}$.

$\displaystyle \therefore 71^{71} \equiv 11 \pmod{17}$ (that is, $\displaystyle x = 11$)

--------

Can you see how I have repeatedly broken the original, gigantic number, into lots of smaller numbers, using Fermat's Generalized Little Theorem as a starting block and using algebra of indices to finish off the work ?

3. Originally Posted by meshel88
71^71 is congruent to x(mod 17)
$\displaystyle 71^71\equiv 3^{71}\equiv 3^{7}$. Continue

4. Oh, how could I miss that, of course you should simplify the base first