Fermat test

  • Thread starter Fairy111
  • Start date
  • #1
73
0

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!
 

Answers and Replies

  • #2
CompuChip
Science Advisor
Homework Helper
4,302
47
It might help to note that 512 = 2^9, so
8^512 = 8^(2^9) = (...(((8^2)^2)^2)...)^2)
 
  • #3
73
0
Im still struggling with this question.

I dont follow the part,

=(...(((8^2)^2)^2)...)^2)
 
  • #4
CompuChip
Science Advisor
Homework Helper
4,302
47
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?
 

Related Threads on Fermat test

  • Last Post
Replies
13
Views
3K
Replies
17
Views
2K
  • Last Post
Replies
9
Views
3K
  • Last Post
Replies
4
Views
924
  • Last Post
Replies
10
Views
1K
  • Last Post
Replies
8
Views
754
Replies
3
Views
6K
Replies
7
Views
956
Replies
4
Views
3K
Replies
11
Views
9K
Top