mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2020-09-11, 23:00   #1
bhelmes
 
bhelmes's Avatar
 
Mar 2016

28710 Posts
Default factors of Mersenne numbers

If f | Mp and p is prime then

a) f | 2n²-1

b) but not f=2n²-1


a) is clear for me but b) is a guess (I checked some numbers)


The first and fastest counterexample is welcome (Or a proof ?)


Greetings,

there must be somewhere a new Mersenne Prime
Bernhard
bhelmes is offline   Reply With Quote
Old 2020-09-12, 01:05   #2
masser
 
masser's Avatar
 
Jul 2003
wear a mask

13·113 Posts
Default

Quote:
Originally Posted by bhelmes View Post
If f | Mp and p is prime then

a) f | 2n²-1

b) but not f=2n²-1
What is n?
masser is offline   Reply With Quote
Old 2020-09-12, 01:09   #3
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

1110110110102 Posts
Default

Quote:
Originally Posted by bhelmes View Post
If f | Mp and p is prime then

a) f | 2n²-1

b) but not f=2n²-1


a) is clear for me but b) is a guess (I checked some numbers)


The first and fastest counterexample is welcome (Or a proof ?)
First example: Taking n = 1, f = 1 divides 2p - 1 for any p.

First example with prime f: p = 3, n = 2; f = 2*22 - 1 = 7 divides 23 - 1 = 7.

Second example with prime f: p = 5, n = 4; f = 2*42 - 1 = 31 divides 25 - 1 = 31

48 other examples known where f = 2p - 1 is prime.

Hey, you didn't say f had to be a proper divisor -- or prime.

I checked the factor table of 2n - 1, odd n < 1200, and did not find any examples with f prime other than f = Mp

I didn't check for composite proper factors of the form 2*n2 - 1.

Last fiddled with by Dr Sardonicus on 2020-09-12 at 01:10 Reason: xingif posty
Dr Sardonicus is offline   Reply With Quote
Old 2020-09-12, 06:07   #4
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22×7×11×29 Posts
Default

Quote:
Originally Posted by masser View Post
What is n?
Quote:
Originally Posted by Dr Sardonicus View Post
Hey, you didn't say f had to be a proper divisor -- or prime.
His "framework" is known, he is "barking at the same tree" for few years by now.

Here, n is any integer.

What he tries to do for a while by now, is to find a previously unknown, non trivial, factor of a mersenne number in gimps' range, based on the fact that all mersenne numbers with odd exponent are the form 2n^2-1, and based on the fact that the series s(n)=2n^2-1 for integer n, is a divisibility series. So, if you write all of them in a row, from 1 to infinity, you can sieve them, and extract the factors. In this series, mersenne numbers with prime exponents appear at indexes powers of two. For example, m=M11=2^11-1=2*((2^5)^2)-1 appears at index 2^5=32. In the same time, m is divisible by 23, therefore s(32) is divisible by 23. But, because this is a divisibility series, if s(x) is divisible by some q for some particular x, then s(x+q), s(x-q), s(x+aq), s(x-aq), s(-x), ......, etc, are all divisible by q, for any integer a. Therefore, s(32-23)=s(9) is also divisible by 23. Indeed, s(9)=2*9^2-1=161, which is 7*23, and it is much smaller than 2047. When you sieve this series with primes, after sieving with just few primes (here, 7 is the third odd prime) you find 23 at index 9, and you just factored M11.

This works fine for small numbers, but it becomes laborious for the range where we work now with TF -- to have any chance to find a 75 bit factor, you have to sieve and parse this string up to 2^50 terms or so.

Current gimps methods are much faster. But he might get lucky, as I told him in the past many times. I think is is still searching this, but he didn't come yet with a previously unknown, non trivial factor, in gimps range (i.e. exponent smaller than 1G).

So, the second question in fact, asks for which n the order of 2 in 2*n^2-1 is prime, which is indeed true only for primes


(this thread is more like misc math)

Last fiddled with by LaurV on 2020-09-12 at 06:22
LaurV is offline   Reply With Quote
Old 2020-09-13, 02:05   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

10111001100102 Posts
Default

Quote:
Originally Posted by bhelmes View Post
If f | Mp and p is prime then

a) f | 2n²-1

b) but not f=2n²-1


a) is clear for me but b) is a guess (I checked some numbers)


The first and fastest counterexample is welcome (Or a proof ?)
2*2^2-1 | 2^3-1
CRGreathouse is offline   Reply With Quote
Old 2020-09-13, 04:53   #6
bhelmes
 
bhelmes's Avatar
 
Mar 2016

4378 Posts
Default

f should be a proper divisor from the non prime Mp,
where Mp is a Mersenne number with prime p.
bhelmes is offline   Reply With Quote
Old 2020-09-13, 06:12   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

173216 Posts
Default

Quote:
Originally Posted by bhelmes View Post
f should be a proper divisor from the non prime Mp,
where Mp is a Mersenne number with prime p.
In that case, I don't find any examples below the unfactored composite Mp = 2^1213 - 1.
CRGreathouse is offline   Reply With Quote
Old 2020-09-13, 09:34   #8
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

2428 Posts
Question

Quote:
Originally Posted by LaurV View Post
and based on the fact that the series s(n)=2n^2-1 for integer n, is a divisibility series.
How? For example, 7 divides 70, but s(7) = 2*7^2 - 1 = 97 does not divide s(70) = 2*70^2 - 1 = 9799. Clearly enough, 97 divides 9797, hence 97 leaves a remainder of 2 when dividing into 9799?

It is true that M(p) = 2^p - 1, for odd p, can be written as s(n); you take n = 2^{(p-1)/2}.

For example, M(101) = 2^101 - 1 = 2*(2^50)^2 - 1 = s(2^50).

Not sure if the relation n = 2^{(p-1)/2} is related to masser's question.

/JeppeSN
JeppeSN is offline   Reply With Quote
Old 2020-09-14, 17:36   #9
bhelmes
 
bhelmes's Avatar
 
Mar 2016

7·41 Posts
Default

Quote:
Originally Posted by JeppeSN View Post
How?

You did not understand the algorithm.
Have a look at :
http://devalco.de/quadr_Sieb_2x%5E2-1.php


I improved the page and hope that the content is well described,
if you have improvements, tell it to me.
bhelmes is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Modular restrictions on factors of Mersenne numbers siegert81 Math 23 2014-03-18 11:50
Mersenne prime factors of very large numbers devarajkandadai Miscellaneous Math 15 2012-05-29 13:18
Mersenne Prime Factors of v.large numbers devarajkandadai Miscellaneous Math 6 2006-01-04 22:44
Factors of Mersenne Numbers asdf Math 17 2004-07-24 14:00
Factors of Mersenne numbers ? Fusion_power Math 13 2003-10-28 20:52

All times are UTC. The time now is 09:51.

Fri Nov 27 09:51:10 UTC 2020 up 78 days, 7:02, 4 users, load averages: 1.41, 1.41, 1.25

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.