Possible values for k (in Mersenne factors) - Page 7

science_man_88 · 2014-05-05, 12:35

Quote:

Originally Posted by Qubit

2. Recall that if M(p) divides M(q) (p, q are odd primes) then $M(p)\equiv 1 (mod q)$ , which is a contradiction since q cannot divide an even number.

If p divides $M_q\text{, then }2^q = 1\text{ mod p}$ is not equivalent to this. The restatement with $M_p$ and $M_q$ is:

if $M_p | M_q ; 2^q = 1\text{ mod M_p}$ also note that that any number # can divide an even number 2*#

LaurV · 2014-05-05, 13:39

For any m<n, not necessarily prime, if $gcd(m,n)=1$ , then $gcd(2^n-1,\ 2^m-1)=1$
This is very easy to prove, if you assume the last gcd is bigger than 1, let that be x, then you subtract them, so $2^n-1-(2^m-1)=2^n-1-2^m+1=2^n-2^m=2^m(2^{n-m}-1)$ , now x divides both a and b, so x divides a-b. But x is odd so it can't divide $2^m$ so x divides the parenthesis. Repeat with the smallest two from the three: $2^n-1,\ 2^m-1$ , and the parenthesis $2^{n-m}-1$ , and you get Euclid's gcd algorithm at the exponents, therefore x divides 2^1-1=1. Give or take some to avoid RDS's intervention

Qubit · 2014-05-05, 14:22

Quote:

Originally Posted by science_man_88

If p divides $M_q\text{, then }2^q = 1\text{ mod p}$ is not equivalent to this. The restatement with $M_p$ and $M_q$ is:

if $M_p | M_q ; 2^q = 1\text{ mod M_p}$ also note that that any number # can divide an even number 2*#

I didn't say p divides M(q), I said M(p) divides M(q), which does imply $M(p)\equiv 1 (mod q)$ .

As for the second thing, obviously primes also divide even numbers, I have no idea why I said that (it is ridiculously wrong, I apologize).

science_man_88 · 2014-05-05, 14:25

Quote:

Originally Posted by Qubit

I didn't say p divides M(q), I said M(p) divides M(q), which does imply $M(p)\equiv 1 (mod q)$ .

As for the second thing, obviously primes also divide even numbers, I have no idea why I said that (it is ridiculously wrong, I apologize).

all you did was replace p with M(p) do that throughout the reference and you get what I said.

edit:sorry I thought you were looking at the same part I was I see now you weren't

PawnProver44 · 2016-03-10, 19:58

In the case that 2*k*p+1 is a factor of 2^p-1, k = 0 or 3 mod 4.

science_man_88 · 2016-03-10, 20:01

Quote:

Originally Posted by PawnProver44

In the case that 2*k*p+1 is a factor of 2^p-1, k = 0 or 3 mod 4.

is false ...

LaurV · 2016-03-11, 02:09

k=0 or 4-p (mod 4)

PawnProver44 · 2016-03-11, 06:39

About 9.4% of all odd primes are cofactors of Mersenne Numbers with p prime for 2^p-1.

LaurV · 2016-03-11, 07:28

Quote:

Originally Posted by PawnProver44

About 9.4% of all odd primes are cofactors of Mersenne Numbers with p prime for 2^p-1.

Wrong.

Edit: you have 2 factors in 4 primes, below 10 (3 and 7 divide respectively M2 and M3), so 50%.
Under 100, you have 24 odd primes, from which 6 are factors (additional of the above, 23, 31, 47, 89, divide respectively M11, M5, M23, M11). So 25%.
Continuing, with primes under 10^3 you have 22/167=13.1736%
with primes under 10^4 you have 106/1228=8.6319%
with primes under 10^5 you have 386/9591=6.1099%
with primes under 10^6 you have 3846/78497=4.8996%
etc.

So, it goes down fast, the number of primes are logarithmic, etc, therefore about 0% of all odd primes are (co)factors of mersenne numbers with prime exponents.

Edit 2: I still believe you are only trolling, so in a certain point I will stop answering to you.

PawnProver44 · 2016-03-13, 06:29

I am not trolling you. This is common logic I am using here.

gd_barnes · 2016-03-13, 09:27

Quote:

Originally Posted by PawnProver44

I am not trolling you. This is common logic I am using here.

More like idiotic logic.

2014-05-05, 13:39	#68
LaurV Romulan Interpreter Jun 2011 Thailand 2·5·31² Posts	For any m<n, not necessarily prime, if $gcd(m,n)=1$ , then $gcd(2^n-1,\ 2^m-1)=1$ This is very easy to prove, if you assume the last gcd is bigger than 1, let that be x, then you subtract them, so $2^n-1-(2^m-1)=2^n-1-2^m+1=2^n-2^m=2^m(2^{n-m}-1)$ , now x divides both a and b, so x divides a-b. But x is odd so it can't divide $2^m$ so x divides the parenthesis. Repeat with the smallest two from the three: $2^n-1,\ 2^m-1$ , and the parenthesis $2^{n-m}-1$ , and you get Euclid's gcd algorithm at the exponents, therefore x divides 2^1-1=1. Give or take some to avoid RDS's intervention Last fiddled with by LaurV on 2014-05-05 at 13:48 Reason: repaired tex thingies

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Distribution of Mersenne Factors	tapion64	Miscellaneous Math	21	2014-04-18 21:02
Known Mersenne factors	CRGreathouse	Math	5	2013-06-14 11:44
A strange new (?) fact about Mersenne factors	ChriS	Math	14	2006-04-12 17:36
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

2016-03-10, 19:58	#71
PawnProver44 "NOT A TROLL" Mar 2016 California C5₁₆ Posts	In the case that 2kp+1 is a factor of 2^p-1, k = 0 or 3 mod 4.

2016-03-11, 02:09	#73
LaurV Romulan Interpreter Jun 2011 Thailand 10010110001010₂ Posts	k=0 or 4-p (mod 4)

2016-03-11, 06:39	#74
PawnProver44 "NOT A TROLL" Mar 2016 California 197 Posts	About 9.4% of all odd primes are cofactors of Mersenne Numbers with p prime for 2^p-1.

2016-03-13, 06:29	#76
PawnProver44 "NOT A TROLL" Mar 2016 California 11000101₂ Posts	I am not trolling you. This is common logic I am using here.