# Fermat test

## Homework Statement

Use the Fermat test to show that 513 is not a prime number.

## The Attempt at a Solution

What i have so far is:

n=513
Then i pick an 'a' with 1<a<n
Let a=8

So i need to compute a^(n-1) mod n
-> 8^512 mod 513

If 8^512 is not congruent to 1 mod 513, then i have shown 513 is not a prime number.

However i am stuck with how to do this.

Any help would be great thanks!

CompuChip
Homework Helper
It might help to note that 512 = 2^9, so
8^512 = 8^(2^9) = (...(((8^2)^2)^2)...)^2)

Im still struggling with this question.

=(...(((8^2)^2)^2)...)^2)

CompuChip
Homework Helper
I mean, for example, that

(82)2 = 84
(the square of the square is the fourth power),
((82)2)2 = (84)2) = 88,
and so on.

Also, the operation of squaring is "compatible" with modulo calculus, in the sense that
84 (mod x) = (82)2 (mod x) = ((82 (mod x))2 (mod x).
So when you want the modulus of the fourth power, which is the modulus of the square of the square, you can first square once, take the modulus, then square again, and take the modulus (check it, for example take x = 3). You can apply this to find, for example, 8512 (mod 123) without first calculating 8512 (which no common calculator can do).

Does this make sense, so far?