# Fermat test

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

Related Linear and Abstract Algebra News on Phys.org
Hurkyl
Staff Emeritus
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.

Gold Member
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?

Hurkyl
Staff Emeritus
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.

Gold Member
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?

Gold Member
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?

Hurkyl
Staff Emeritus
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.

Gold Member
still dont get it )-: how does it prooves a+kp<p?

sorry to bother you.

Hurkyl
Staff Emeritus