# Fermat test

1. Oct 29, 2009

### Fairy111

1. The problem statement, all variables and given/known data
Use the Fermat test to show that 513 is not a prime number.

2. Relevant equations

3. 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!

2. Oct 29, 2009

### CompuChip

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

3. Oct 31, 2009

### Fairy111

Im still struggling with this question.

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

4. Oct 31, 2009

### CompuChip

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?