Fermat test

  • #1
MathematicalPhysicist
Gold Member
4,308
216
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.
 

Answers and Replies

  • #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
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.
 
  • #3
MathematicalPhysicist
Gold Member
4,308
216
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?
 
  • #4
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
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.
 
  • #5
MathematicalPhysicist
Gold Member
4,308
216
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?
 
  • #6
MathematicalPhysicist
Gold Member
4,308
216
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?
 
  • #7
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
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.
 
  • #8
MathematicalPhysicist
Gold Member
4,308
216
still dont get it )-: how does it prooves a+kp<p?


sorry to bother you.
 
  • #9
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
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 Threads on Fermat test

Replies
2
Views
6K
  • Last Post
2
Replies
27
Views
5K
  • Last Post
Replies
14
Views
4K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
1
Views
3K
  • Last Post
3
Replies
52
Views
10K
  • Last Post
Replies
13
Views
3K
Top