Hi folks
> a simple Number Theory question. Is always
> (2^p-1) / p ,odd prime p, divisible by 3 ?
Those of you who've already answered this question know what Alex meant to ask was
is (M(p)-1)/p divisible by 3, for odd prime p>3.
ie (2^p-2)/p. The answer is yes, since 2^2=1 mod 3, 2^p=2 mod 3, (2^p-2) is divisible
by 3 and hence the result follows.
> Then 2^p == 1 (mod 3p) would also hold, can this be
> used to improve the efficiency of a Rabin-Miller
> probable prime test?
2^p==2.
It wouldn't make a great deal of difference... you might save a few bits in the length
of the exponent, but that isn't a great saving. As far as I can see though the problem
with this reasoning is that the extra factor 3 in the known factor of M(p)-1 doesn't
occur because p is prime, it occurs because p is odd. So it's not actually giving you
any additional information that could improve your test's effectiveness.
Chris Nash
Lexington KY
UNITED STATES
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
