20210903, 00:51  #1 
Mar 2016
3^{2}×41 Posts 
factors of Mersenne numbers
A peaceful and pleasant night for you,
if f>1 is the smallest factor of a Mersenne number, than there exists a n0>1 for the function f(n)=2n²1 where n0 is the minimum, so that f  f(n0) and exactly one prime g with f*g=f(n0) where g<f Is this a correct and (well known) logical statement ? P.S. I am sure we find the next Mp before Christmas ... 
20210903, 01:37  #2  
Feb 2017
Nowhere
5^{3}×41 Posts 
Quote:
True for Mersenne primes greater than 7: If p > 3 is prime, and P = 2^{p}  1 is prime, then f = P, and f divides (2^((p+1)/2))^2  2 = 2*f. Here, g = 2. Note that for p > 3, 2*2^((p+1)/2) = 2^((p+3)/2) < 2^((p+p)/2) = 2^p, so 2^((p+1)/2) <= P/2 = f/2, whence n_{0} = 2^((p+1)/2). Not necessarily true for composite values of 2^{p}  1, p prime. Example: p = 11, 2^{11}  1 = 2047 = 23*89; f = 23, n_{0} = 5, n_{0}^{2}  2 = f. No prime g < f here. 

20210904, 21:29  #3 
Mar 2016
3^{2}·41 Posts 
The statement was not exactly formulated :
if f>1 is the smallest factor of a Mersenne number, than there exists a n0>1 for the function f(n)=2n²1 where n0 is the minimum, so that f  f(n0) and maximal one prime g with f*g=f(n0) where g<f This statement would allow to limit the recursion deep of my algorithm. Thanks if you spend me some lines. P.S. I did some programming but the runtime has to improve further. 
20210905, 01:53  #4 
Feb 2017
Nowhere
5^{3}×41 Posts 
Of course, since n_{0} < f/2, the cofactor (2*n_{0}^2  1)/f < f/2. So if the cofactor is prime, it is certainly less than f.
Since I could think of no reason why the cofactor should always be prime, as a programming exercise I wrote a mindless script to look for counterexamples for 2^p  1 with small prime exponent p. I told it to print out the exponent p, the smallest factor f of 2^p  1, the value n_{0}, and the factorization of the cofactor (2*n_{0}^2  1)/f when this was composite. The smallest exponent giving a counterexample is p = 47. To my surprise, with the smallest example 47 (f = 2351, n_{0} = 240) and 113 (f = 3391, n_{0} = 700) the cofactor (2*n_{0}^2  1)/f is the square of a single prime. The smallest prime exponent for which the cofactor (2*n_{0}^2  1)/f has at least two distinct prime factors is 59. Code:
? { forprime(p=3,200, M=factor(2^p1); f=M[1,1]; m=factormod(2*x^21,f); n=lift(polcoeff(m[1,1],0,x)); if(n+n>f,n=fn); N=factor((2*n^21)/f); if(#N[,1]>1(#N[,1]==1&&N[1,2]>1),print(p" "f" "n" "N)) ) } 47 2351 240 Mat([7, 2]) 59 179951 77079 [7, 1; 9433, 1] 67 193707721 66794868 [191, 1; 241177, 1] 71 228479 76047 [23, 1; 31, 1; 71, 1] 97 11447 5670 [41, 1; 137, 1] 101 7432339208719 3616686326055 [7, 1; 17, 1; 23, 1; 1583, 1; 812401, 1] 103 2550183799 270087243 [23, 1; 241, 1; 10321, 1] 109 745988807 298036466 [17, 1; 14008369, 1] 113 3391 700 Mat([17, 2]) 137 32032215596496435569 6857964810884905735 [2503, 1; 358079, 1; 3276376633, 1] 151 18121 2513 [17, 1; 41, 1] 163 150287 31486 [79, 1; 167, 1] 173 730753 162850 [7, 1; 10369, 1] 179 359 170 [7, 1; 23, 1] 193 13821503 2664653 [7, 1; 146777, 1] 199 164504919713 50650852663 [7, 1; 4455809207, 1] ? 
20210913, 00:58  #5  
Mar 2021
2^{2}·11 Posts 
Quote:
Just pointing this out as i found you post informing and wanted to point out the formula for generating the factors of prime numbers which are then used to create a mersenne number. You may already know this but just wanting to point it out to those interested in where those numbers ( factors ) come from. On a side note, kind of wondering if trial division for mersenne numbers employ this climbing technique already as it chops out a lot of unnecessary tests Quote:
Last fiddled with by LarsNet on 20210913 at 01:29 

20210913, 02:49  #6 
Romulan Interpreter
"name field"
Jun 2011
Thailand
23120_{8} Posts 

20210913, 14:18  #7  
Feb 2017
Nowhere
5^{3}·41 Posts 
Quote:
1) If k is odd and composite, not all prime factors of 2^k  1 are congruent to 1 (mod 2k). If dk, the prime factors of the "primitive part" of are congruent to 1 (mod 2d). They do not have to be congruent to 1 (mod 2k). For example, the factor 2^3  1 = 7 of 2^39  1 is congruent to 1 (mod 6) but not congruent to 1 (mod 78); and the factor 2^5  1 = 31 of 2^65  1 is congruent to 1 (mod 10) but not congruent to 1 (mod 65). 2) If p is an odd prime, it is well known that the prime factors of 2^p  1 are congruent to 1 (mod 2p), and also congruent to 1 or 7 (mod 8). 3) If p is of any size at all, trial division up to the square root of 2^p  1 is totally impracticable. 4) Also, if p is of any size at all, the number of candidates q == 1 (mod 2p) and 1 or 7 (mod 8) can be reduced significantly by excluding those with small prime factors. I incorporated the facts in (2) into an otherwise totally mindless PariGP script. I wrote the script in a text editor and filled in the exponent by hand for each run, and copypasted it into a PariGP session. I didn't bother trying to code user input. Code:
{ p = 67; n = 2^p  1; q=1; r=p%4; r=4r; a = 8*r*p; d=2*r*p; q=1; c=0; m=1; until(m==0c>1000000, q+=d; c++; d=ad; m=n%q; if(m==0, print("Try number "c" found the factor "q" of 2^"p"  1.") ); if(c>1000000,print("No factors found in a million tries.")) ) } Try number 722790 found the factor 193707721 of 2^67  1. ? { p = 101; n = 2^p  1; q=1; r=p%4; r=4r; a = 8*r*p; d=2*r*p; q=1; c=0; m=1; until(m==0c>1000000, q+=d; c++; d=ad; m=n%q; if(m==0, print("Try number "c" found the factor "q" of 2^"p"  1.") ); if(c>1000000,print("No factors found in a million tries.")) ) } No factors found in a million tries. ? 

20210913, 15:34  #8  
Mar 2021
2^{2}×11 Posts 
Quote:
In [3396]: getfactorsfromoffset2(2**671) 722789 193707721 Factor Found Offset for each jump is bit_length 67 I'll look at installing pari gp see if i can follow what your doing EDIT, oh there is this cool online interpreter at the pari/gp site, i'll look at that first Last fiddled with by Uncwilly on 20210913 at 17:12 Reason: removed much of huge quote 

20210913, 18:28  #10 
Mar 2021
2^{2}·11 Posts 
While i'm learning PARI/GP, i added a runnable version of this on replit:
https://replit.com/@oppressionslyr/M...arison#main.py You can change the bottom number to other numbers other than 2**431 and hit run again. This is not using gmpy2 (so is slow) and will not work with 2**491 since 127 factor is lower , than the first equations answer of (46+471)*2+3 and ((46+471)+1)*2+3. I'm sure i could tweak the offset to fix that if needed. My suggestion is to stay below 2**711, just because it's slow for larger numbers THIS VERSION finds all factors instead of the first which i posted, all climbing from the same offset of the bit_length() 
20210913, 18:53  #11  
Mar 2021
2^{2}·11 Posts 
Quote:
Like this : Quote:
Sorry if i posted something well known, i discovered this without knowing it, so thought it was useful. Also, would mine not be twice as fast due to the equation i use to get the larger number prime quicker, i'm actually ahead of the jump by the exponent by a factor of 2, lol Just go with me on this, if you look at the right column, i'm jumping by twice the exponent and arriving at correct answers, that second column moves up by twice the bit_length or exponent which are the same. Maybe thats different? I wish i knew how to do emoticons, i'd put one here, that seems cool. I'm really not trying to sound like i've found anything revolutionary here, its just fun to point out ( which probably means my math is wrong, i'll look into that ( which it is i just verified, i should be looking at twice the bit_length and i'm looking at double it ) Last fiddled with by LarsNet on 20210913 at 19:43 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Factors for the differences between Mersenne numbers  a nicol  Miscellaneous Math  1  20201015 09:53 
factors of Mersenne numbers  bhelmes  Miscellaneous Math  8  20200914 17:36 
Mersenne Prime Factors of v.large numbers  devarajkandadai  Miscellaneous Math  6  20060104 22:44 
Factors of Mersenne Numbers  asdf  Math  17  20040724 14:00 
Factors of Mersenne numbers ?  Fusion_power  Math  13  20031028 20:52 