Thread: factors of Mersenne numbers View Single Post
2021-09-14, 12:30   #20
Dr Sardonicus

Feb 2017
Nowhere

2×2,503 Posts

Quote:
Originally Posted by LarsNet
Quote:
 Originally Posted by Dr Sardonicus Just to be clear, the lines were marked "Wasted effort" because the candidates were congruent to 3 or 5 (mod 8), hence ineligible. Simply avoiding those candidates would cut the run time of your routine approximately in half.
Thanks for that info. I am interested in this for personal reasons,so i'll try that out
I can not improve on the sources already cited. The information you are thanking me for here, I had already given you in a previous post, and is also in the reference with link provided in this post. It is disappointing to see you have not been availing yourself of the information we have been spending time and effort to make easily available to you.

What I would implore you to consider, is the fact that people have been thinking about this subject for a long, long time, and it is therefore not only possible, but very likely, that any elementary result anyone discovers these days, has already been known for many years.

While it can be disappointing to the re-discoverer to learn that their fresh, new discovery has actually been known for centuries, it should also be reassuring to realize that their rediscovery is at least correct. It's happened to me. It's probably happened to just about everyone who's done serious work in mathematics or math-based projects.

Then there is the matter of coding. I would consider my own Pari script as nothing more than illustrative of the results (1) and (2) below for small prime exponents p. For serious effort at finding factors, I would recommend using the software provided by people who have familiarized themselves with the known mathematical results, understand how computers do what they do, and have for decades been writing, optimizing, and debugging code to do trial factorization, etc of Mersenne numbers.

Let p be an odd prime, and q an odd prime such that q divides 2p - 1.

1) Then (Fermat's "little theorem") q divides 2q-1 - 1. It follows that p divides q-1.
Proof (probably known to Fermat, certainly to Euler) left as exercise. Feel free to look it up. Note: Since p is odd and q-1 is even, 2p also divides q-1.

2) q == 1 or 7 (mod 8).
Sketch of proof: Since 2p divides q - 1, p divides $\frac{q-1}{2}$. Thus, since q divides 2p - 1, q also divides $2^{\frac{q-1}{2}}\;-\;1$. Therefore, 2 is a quadratic residue (mod q), and the result follows. Note: This certainly would have been known to Gauss.

3) Let k be a positive integer. Suppose p = 4*k + 3 and q = 2p + 1 = 8*k + 7 are both prime. Then q divides 2p - 1. Proof left as exercise. Hint: Apply result (2).

Note: Whether there are infinitely many k for which p = 4*k + 3 and q = 2*p + 1 = 8*k + 7 are both prime, is an open question. There are conjectured asymptotic formulas, supported by limited numerical data, that would say "Yes" to this and a host of similar questions. The conjectures indicate that the proportion of prime p = 4*k + 3 for which q = 8*k + 7 is also prime, slowly decreases toward 0 as k increases without bound.

Last fiddled with by Dr Sardonicus on 2021-09-14 at 12:32 Reason: insert missing word; fignix posty