Fermat test

MathematicalPhysicist

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.

MathematicalPhysicist

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.

MathematicalPhysicist

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?

MathematicalPhysicist

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.

MathematicalPhysicist

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

sorry to bother you.

Hurkyl

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

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving