## Mersenne numbers

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

### Mersenne numbers

I was looking at mersenne numbers and I found the theorem: if p and 2p+1 are prime and p is congruent to 3(mod 4) then 2p+1|2p-1. This can be used to aid the search for mersenne primes by narrowing down the search. I was wondering, are there any other ways to narrow down the search for mersenne primes? For example, I thought I had discovered that if p and 6p+1 are prime, and p is congruent to 1(mod 18), then 6p+1|2p-1 (the first counter-example is p=181)
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
tomtom2357

Posts: 427
Joined: Tue Jul 27, 2010 8:48 am UTC

### Re: Mersenne numbers

Talith wrote:If p is prime then surely p=1 (mod n) for all n<p.
First counterexample to that is 5. Followed by all the other primes.
In the future, there will be a global network of billions of adding machines.... One of the primary uses of this network will be to transport moving pictures of lesbian sex by pretending they are made out of numbers.
Spoiler:
gmss1 gmss2

gmalivuk
Archduke Vendredi of Skellington the Third, Esquire

Posts: 19274
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here, There, Everywhere (near Boston, anyway)

### Re: Mersenne numbers

Did something get deleted?
#xkcd-q — a pretty neat LGBTQIQ channel on Foonetic

"Grant me chastity and continence, but not yet." —St. Augustine

Ceterum autem censeo, Yalensem esse delendam.

TheGrammarBolshevik
waldo waldorf waldron waldron's wale waler wales waley walfish walford walgreen walhalla

Posts: 4258
Joined: Mon Jun 30, 2008 2:12 am UTC
Location: Where.

### Re: Mersenne numbers

TheGrammarBolshevik wrote:Did something get deleted?

That was my guess.

Proginoskes

Posts: 309
Joined: Mon Nov 14, 2011 7:07 am UTC
Location: Sitting Down

### Re: Mersenne numbers

Mods quoting a soft deleted post cos I knew how wrong I was below the belt.

Talith
Proved the Goldbach Conjecture

Posts: 844
Joined: Sat Nov 29, 2008 1:28 am UTC
Location: Manchester - UK

### Re: Mersenne numbers

oops, the soft-delete notice looks unfortunately similar to the edit notice, so I don't really pay attention that much.
In the future, there will be a global network of billions of adding machines.... One of the primary uses of this network will be to transport moving pictures of lesbian sex by pretending they are made out of numbers.
Spoiler:
gmss1 gmss2

gmalivuk
Archduke Vendredi of Skellington the Third, Esquire

Posts: 19274
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here, There, Everywhere (near Boston, anyway)

### Re: Mersenne numbers

Every test for prime numbers (and especially for mersenne numbers) is a way to narrow down the search. They are just different in efficiency and required computing power.
mfb

Posts: 803
Joined: Thu Jan 08, 2009 7:48 pm UTC

### Re: Mersenne numbers

I was looking for ways to eliminate potential possibilities by using results akin to the one I gave in my first post, possibly combined with the fact that the only possible divisors of 2p-1 are of the form 2kp+1. The result I mentioned considers the cases where k=1, but I would like to know under what conditions k equals another specific integer.

Edit: Also this is a quick way to eliminate possible candidates, as this only needs to check if two small (a.k.a, less than 1 billion) numbers are prime, and that p satisfies a modular congruence. The first can easily be done by checking a table of prime numbers, and the second does not require much computing power. The Lucas-Lehmer-primality test can take months, so I would think that taking a few seconds to check if the Lucas-Lehmer test is required is better than running it for all values.

Edit 2: I discovered the proof of the first theorem (if p and q=2p+1 are prime, and p=3(mod 4), then q|2p-1), it relies on the fact that 2 is a quadratic residue mod q if q=7(mod . Let n2=2(mod q), then 2p-1=2(q-1)/2-1=n(q-1)-1(mod q)=0(mod q) (the last congruence is just Fermat's Little Theorem).

I can tweak this theorem for deciding when q=6p+1|2p-1 (assuming q is prime): if 2 is a hexic residue mod q, let n6=2(mod q) then 2p-1=2(q-1)/6-1=nq-1-1(mod q)=0(mod q). Now to decide which q have 2 as a hexic residue. Any ideas?

Edit 3: I have an (unproved) theory: a number n is a hexic residue mod q iff n is a quadratic and cubic residue mod q. This combined with the fact that q=1(mod3) is the only q that we need to consider, and a fact from wikipedia that says: 2 is a cubic residue mod q iff q=27a2+b2, and 2 is a quadratic residue mod q iff q=+-1(mod8). p is prime, and is therefore odd (p=2 is a special case), so q=6p+1=3(mod4), so q=7(mod24) (by the quadratic residue requirement), so p=1(mod4). Therefore the requirement is that p=1(mod4), and q=27a2+b2.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
tomtom2357

Posts: 427
Joined: Tue Jul 27, 2010 8:48 am UTC