mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2019-04-26, 09:22   #1
jnml
 
Feb 2012
Prague, Czech Republ

2×34 Posts
Default Constraints on k in 2kp+1

If n \in \mathbb{N} divides a Mersenne number M_p, prime p, then n can be written as 2kp+1, \: k \in \mathbb{N}.

IIUC, it can be shown that k \: \ne \: 2 \: (\bmod \: 4). Additionally I think I've
seen somewhere that k \: \ne \: 0 \:(\bmod \: p) when k \: \ne \: 0.

Q: Are there other known constraints? Or any other interesting properties of k?
jnml is offline   Reply With Quote
Old 2019-04-26, 12:56   #2
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

22·7·103 Posts
Default

k=0 (mod p) is ok but only 1 known example p=93077.
ATH is online now   Reply With Quote
Old 2019-04-26, 13:15   #3
Brian-E
 
Brian-E's Avatar
 
"Brian"
Jul 2007
The Netherlands

2×23×71 Posts
Default

Quote:
Originally Posted by ATH View Post
k=0 (mod p) is ok but only 1 known example p=93077.
I see that for this factor 11686604129694847 we have k divisible not just by p but by p^2 . Could this be a requirement if k=0 (mod p) ?
Brian-E is offline   Reply With Quote
Old 2019-04-26, 13:27   #4
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·11·151 Posts
Default

For p > 2,

M_{p}\;=\;2\times [2^{\frac{p-1}{2}}]^{2} - 1

so 2 is a quadratic residue of every prime divisor q, whence q == 1 or -1 (mod 8). Consequently, if

q = 2*k*p + 1, then

k == 0 (mod 4) (q == 1 (mod 8)) or

k == -p (mod 4) (q == -1 (mod 8)).
Dr Sardonicus is offline   Reply With Quote
Old 2019-04-26, 14:05   #5
DukeBG
 
Mar 2018

3·43 Posts
Default

Quote:
Originally Posted by Brian-E View Post
I see that for this factor 11686604129694847 we have k divisible not just by p but by p^2 . Could this be a requirement if k=0 (mod p) ?
That's what k=0 (mod p) means...

11686604129694847 = 1 + 2 · 3^4 · 11 · 757 · 93077^2

Edit: Which is to say, k is not divisible by p^2 in this example, factor minus one is divisible by p^2.

Last fiddled with by DukeBG on 2019-04-26 at 14:08
DukeBG is offline   Reply With Quote
Old 2019-04-26, 14:19   #6
DukeBG
 
Mar 2018

12910 Posts
Default

In case it'll be of interest, a little intuition about why 2kp+1, where it comes from... For any prime number f, we'll have M(f-1) being divisible by f because Fermat's little theorem. Also you know (very easy to show) that M(x) | M(x * y). So the number f might be divisible in M(f-1) because it's a factor of some M(n) where n | f-1. Thus for M(p), their factors have p | f-1. I.e. f = 1 mod p. I.e. f=k'*p+1. However, f is obviously odd, so k' should be even, so we can write it as 2k or f=2kp+1.

Last fiddled with by DukeBG on 2019-04-26 at 14:19
DukeBG is offline   Reply With Quote
Old 2019-04-26, 14:20   #7
Brian-E
 
Brian-E's Avatar
 
"Brian"
Jul 2007
The Netherlands

2×23×71 Posts
Default

Quote:
Originally Posted by DukeBG View Post
That's what k=0 (mod p) means...

11686604129694847 = 1 + 2 · 3^4 · 11 · 757 · 93077^2

Edit: Which is to say, k is not divisible by p^2 in this example, factor minus one is divisible by p^2.
Yes, in this example k is divisible by p^2, which is to say k=0 (mod p^2).

I am asking if it is known that if k=0 (mod p) then k=0 (mod p^2) (for k<>0).
Brian-E is offline   Reply With Quote
Old 2019-04-26, 14:22   #8
DukeBG
 
Mar 2018

2018 Posts
Default

What do you think k is in this example? 3^4 · 11 · 757 · 93077 is not divisible by 93077^2.
DukeBG is offline   Reply With Quote
Old 2019-04-26, 14:30   #9
Brian-E
 
Brian-E's Avatar
 
"Brian"
Jul 2007
The Netherlands

2·23·71 Posts
Default

Quote:
Originally Posted by DukeBG View Post
What do you think k is in this example? 3^4 · 11 · 757 · 93077 is not divisible by 93077^2.
k=3^4 . 11 . 757 . 93077^2

p=93077

According to ATH p=93077 is the only known example where p|k. However I also observed that p^2 | k. Is that just a monstrous coincidence? Or is it necessary?
Brian-E is offline   Reply With Quote
Old 2019-04-26, 14:59   #10
Brian-E
 
Brian-E's Avatar
 
"Brian"
Jul 2007
The Netherlands

2·23·71 Posts
Default

Apologies!
I've totally misunderstood what k was and that led to a breakdown of communications.
Ignore my posts please.
Brian-E is offline   Reply With Quote
Old 2019-04-26, 15:03   #11
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

22·7·103 Posts
Default

There is no other GIMPS factor p<1B with this property and I also searched a bit beyond GIMPS limits without finding any other examples.

Last fiddled with by ATH on 2019-04-26 at 15:04
ATH is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
solving modular constraints Joshua2 Homework Help 12 2010-02-19 22:59

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

Sat Aug 8 20:09:15 UTC 2020 up 22 days, 15:56, 1 user, load averages: 1.01, 1.40, 1.50

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.