# Fermat test

by MathematicalPhysicist
Tags: fermat, test
 P: 3,243 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.
 Emeritus Sci Advisor PF Gold P: 16,091 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.
P: 3,243
 Originally posted by Hurkyl So, by the virtue of modulo arithmetic, we only need to check values of a that are less than p.
why is it that?

 Emeritus Sci Advisor PF Gold P: 16,091 Fermat test 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.
P: 3,243
 Originally posted by Hurkyl 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.
x is integer?
P: 3,243
 Originally posted by Hurkyl (a+kp)n = an for all n.
excuse my ignorance but how does this proove you only need to check values of a smaller than p?
 Emeritus Sci Advisor PF Gold P: 16,091 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.
 P: 3,243 still dont get it )-: how does it prooves a+kp
 Emeritus Sci Advisor PF Gold P: 16,091 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).

 Related Discussions General Physics 0 Linear & Abstract Algebra 2 Linear & Abstract Algebra 6 General Physics 54 General Math 2