1. Not finding help here? Sign up for a free 30min 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!

Fermat test

  1. Nov 1, 2003 #1
    i read the book "the man who loved only numbers" by paul hoffman, and there is explanation about fermat's test for checking prime numbers which states: if n is prime then for every whole number a the number a^n-a is a multiple of n.
    now my question is about a pseduo prime number which "fools" this test how could you find such a number, i mean you should check every a wich is ofcourse infinite numbers how could you possibly know that n is pseduo prime number by not checking every a?

    btw the smallest p.p number is 561.
     
  2. jcsd
  3. Nov 1, 2003 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    The statement

    ap - a is a multiple of p

    is equivalent to

    ap = a (modulo p)


    So, by the virtue of modulo arithmetic, we only need to check values of a that are less than p.

    There are probably much more efficient theoretical tests for pseudoprimes, but my number theory book is at work so I can't look them up.
     
  4. Nov 1, 2003 #3
    why is it that?
     
  5. Nov 1, 2003 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I'll presume it's obvious that px = 0 mod p.


    Consider this:

    (a+kp)b = ab + kpb = ab (mod p)

    Letting b = (a+kp)i, you can prove by induction that

    (a+kp)n = an for all n.
     
  6. Nov 1, 2003 #5
    x is integer?
     
  7. Nov 1, 2003 #6
    excuse my ignorance but how does this proove you only need to check values of a smaller than p?
     
  8. Nov 1, 2003 #7

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Because

    ap = a (mod p)

    iff

    (a+kp)p = a+kp (mod p)


    P.S. all those little p's are supposed to be exponents.
     
  9. Nov 1, 2003 #8
    still dont get it )-: how does it prooves a+kp<p?


    sorry to bother you.
     
  10. Nov 1, 2003 #9

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    It doesn't.

    Once we've checked all values of a less than p, this theorem extends our results to any other value of a because any integer n can be written as m + pk for some integer m in [0, p).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Fermat test
  1. Fermat proof (Replies: 6)

  2. Fermat's equation. (Replies: 14)

  3. Fermat's theorem (Replies: 1)

  4. Fermat primes (Replies: 27)

Loading...