View Single Post
Old 2021-05-14, 23:50   #18
R. Gerbicz
R. Gerbicz's Avatar
"Robert Gerbicz"
Oct 2005

2·32·83 Posts

Originally Posted by a1call View Post
Aren't all Mersenne-numbers with Prime-exponents, Fermat's-Probable-Prime in base 2^n?
That is true.
For any N if you consider the b bases for that N is a Fermat pseudoprime then these bases form a group in Z_N.
For Mersenne numbers this means that 2^n is such a base, because mp is a Fermat pseudoprime for base=2, fortunately
these means only p such bases, because 2^p==2^0 mod mp.

In an elementary way without group:
you need: (2^n)^(2^p-1)==2^n mod (2^p-1)

but we have: 2^p=a*p+2

hence: (2^n)^(2^p-1)==2^(n*(a*p+1))==2^n mod (2^p-1)
what we needed.

ps. this is the reason why we are using base=3 for Fermat testing the Mersenne numbers, base=2,4,8 etc is "bad". But you shouldn't fix base=3 to all numbers, because for other type of numbers: N could be a (trivial) pseudoprime for base=3, and you need to choose another base.
R. Gerbicz is offline   Reply With Quote