Mersenne numbers

[tomtom2357]

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|2^p-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|2^p-1 (the first counter-example is p=181)

[gmalivuk]

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.

[TheGrammarBolshevik]

Did something get deleted?

[Proginoskes]

Did something get deleted?

That was my guess.

[Talith]

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

[gmalivuk]

oops, the soft-delete notice looks unfortunately similar to the edit notice, so I don't really pay attention that much.

[mfb]

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.

[tomtom2357]

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 2^p-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|2^p-1), it relies on the fact that 2 is a quadratic residue mod q if q=7(mod . Let n²=2(mod q), then 2^p-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|2^p-1 (assuming q is prime): if 2 is a hexic residue mod q, let n⁶=2(mod q) then 2^p-1=2^(q-1)/6-1=n^q-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=27a²+b², 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=27a²+b².