Re: 3^n and primes

quasi <quasi@xxxxxxxx> writes:

On Mon, 02 Jul 2007 19:50:49 -0700, rer <reriker@xxxxxxxxx> wrote:

This is clearly not efficient, but seems curious. However, I am
unable to explore it further because of rounding errors. I hope
someone out there with a bigger number cruncher is curious, too, and
will see if this just dies out quickly, or has something more too it.

Consider 3^n where n is an integer greater than or equal to 2.

Then let p+q = 3^n, such that p, q are consecutive integers

i.e. p=(3^n-1)/2 and q = (3^n+1)/2.

If 2n+1 evenly divides p or q, then 2n+1 is prime

It fails occasionally.

For n<1000, it fails for the following 5 values of n:

n = 60, 351, 770, 864, 945

Let m = 2n+1. m is called a "weak probable prime to base 3" if
m divides 3^(m-1) - 1 = (3^n - 1)(3^n + 1). In particular
this happens if m divides p or q. So your numbers are probable
primes, but not necessarily primes.

Actually m is an "Euler probable prime to base 3" if either
m == 1 or 11 mod 12 and m divides p, or m == 5 or 7 mod 12 and
m divides q.

Of the exceptions quasi found, the only one that doesn't correspond
to an Euler probable prime is n=770, m=1541, since 1541 == 5 mod 12
but divides 3^770 - 1 instead of 3^770 + 1.
--
Robert Israel israel@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada V6T 1Z2
.

Relevant Pages