# Math Help - another mod

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 $gcd(a, m) = 1$, $a^{\varphi{(m)}} \equiv 1 \pmod{m}$, where $\varphi{(m)}$ is the Euler totient of $m$.

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

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

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

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

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

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

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

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

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

And we are done ! We can now write :

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

$\therefore 71^{71} \equiv 11 \pmod{17}$ (that is, $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)
$71^71\equiv 3^{71}\equiv 3^{7}$. Continue

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