1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Fermat test

  1. Oct 29, 2009 #1
    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:

    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. jcsd
  3. Oct 29, 2009 #2


    User Avatar
    Science Advisor
    Homework Helper

    It might help to note that 512 = 2^9, so
    8^512 = 8^(2^9) = (...(((8^2)^2)^2)...)^2)
  4. Oct 31, 2009 #3
    Im still struggling with this question.

    I dont follow the part,

  5. Oct 31, 2009 #4


    User Avatar
    Science Advisor
    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?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook