Register to reply

Fermat test

by MathematicalPhysicist
Tags: fermat, test
Share this thread:
MathematicalPhysicist
#1
Nov1-03, 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^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
Bees able to spot which flowers offer best rewards before landing
Classic Lewis Carroll character inspires new ecological model
When cooperation counts: Researchers find sperm benefit from grouping together in mice
Hurkyl
#2
Nov1-03, 10:49 AM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,092
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
#3
Nov1-03, 11:12 AM
P: 3,221
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
#4
Nov1-03, 11:36 AM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
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 = an for all n.
MathematicalPhysicist
#5
Nov1-03, 11:44 AM
P: 3,221
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
#6
Nov1-03, 12:04 PM
P: 3,221
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
#7
Nov1-03, 12:09 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,092
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
#8
Nov1-03, 12:18 PM
P: 3,221
still dont get it )-: how does it prooves a+kp<p?


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