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(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(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
, 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
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.