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