fermat test


by MathematicalPhysicist
Tags: fermat, test
MathematicalPhysicist
MathematicalPhysicist is offline
#1
Nov1-03, 03:55 AM
P: 3,173
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.
Phys.Org News Partner Science news on Phys.org
Better thermal-imaging lens from waste sulfur
Hackathon team's GoogolPlex gives Siri extra powers
Bright points in Sun's atmosphere mark patterns deep in its interior
Hurkyl
Hurkyl is offline
#2
Nov1-03, 10:49 AM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,101
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
MathematicalPhysicist is offline
#3
Nov1-03, 11:12 AM
P: 3,173
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
Hurkyl is offline
#4
Nov1-03, 11:36 AM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,101

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.
MathematicalPhysicist
MathematicalPhysicist is offline
#5
Nov1-03, 11:44 AM
P: 3,173
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
MathematicalPhysicist is offline
#6
Nov1-03, 12:04 PM
P: 3,173
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
Hurkyl is offline
#7
Nov1-03, 12:09 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,101
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
MathematicalPhysicist is offline
#8
Nov1-03, 12:18 PM
P: 3,173
still dont get it )-: how does it prooves a+kp<p?


sorry to bother you.
Hurkyl
Hurkyl is offline
#9
Nov1-03, 12:35 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,101
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).


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