71^71 is congruent to x(mod 17)

Results 1 to 4 of 4

- February 22nd 2010, 04:10 PM #1

- Joined
- Feb 2010
- Posts
- 21

- February 22nd 2010, 07:08 PM #2
Hello,

use Euler's generalization of Fermat's Little Theorem : if and only if , , where is the Euler totient of .

In your case, is a prime number (lucky you), so . And . Therefore, . Good.

Now note that . Plug in the result you found with Euler's generalization, you find that :

.

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

.

You can easily compute , so :

is not too big and can be computed quickly (if not, break it into two pieces), so . While we're at it, . We get :

.

And we are done ! We can now write :

.

(that is, )

--------

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 ?

- February 22nd 2010, 07:13 PM #3

- February 22nd 2010, 08:41 PM #4