Register to reply 
Fermat test 
Share this thread: 
#1
Nov103, 03:55 AM

P: 3,221

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^na 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
Nov103, 10:49 AM

Emeritus
Sci Advisor
PF Gold
P: 16,092

The statement
a^{p}  a is a multiple of p is equivalent to a^{p} = 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
Nov103, 11:12 AM

P: 3,221




#4
Nov103, 11:36 AM

Emeritus
Sci Advisor
PF Gold
P: 16,092

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} = a^{n} for all n. 


#5
Nov103, 11:44 AM

P: 3,221




#6
Nov103, 12:04 PM

P: 3,221




#7
Nov103, 12:09 PM

Emeritus
Sci Advisor
PF Gold
P: 16,092

Because
a^{p} = a (mod p) iff (a+kp)^{p} = a+kp (mod p) P.S. all those little p's are supposed to be exponents. 


#8
Nov103, 12:18 PM

P: 3,221

still dont get it ): how does it prooves a+kp<p?
sorry to bother you. 


Register to reply 
Related Discussions  
Optica!~and Fermat  General Physics  0  
A primality test for Fermat numbers faster than Pépin's test ?  Linear & Abstract Algebra  2  
Fermat proof  Linear & Abstract Algebra  6  
Fermat and Space  General Physics  54  
Did Fermat proof the Fermat's Last Theorem?  General Math  2 