Solving the Fermat Test for 513: Is it Prime?

[Fairy111]

Homework Statement

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

Homework Equations

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]

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

 

[Fairy111]

Im still struggling with this question.

I don't follow the part,

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

 

[CompuChip]

I mean, for example, that

(8²)² = 8⁴
(the square of the square is the fourth power),
((8²)²)² = (8⁴)²) = 8⁸,
and so on.

Also, the operation of squaring is "compatible" with modulo calculus, in the sense that
8⁴ (mod x) = (8²)² (mod x) = ((8² (mod x))² (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, 8⁵¹² (mod 123) without first calculating 8⁵¹² (which no common calculator can do).

Does this make sense, so far?