mersenneforum.org Constraints on k in 2kp+1
 Register FAQ Search Today's Posts Mark Forums Read

 2019-04-26, 09:22 #1 jnml   Feb 2012 Prague, Czech Republ 2448 Posts 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$?
 2019-04-26, 12:56 #2 ATH Einyen     Dec 2003 Denmark 3×5×199 Posts k=0 (mod p) is ok but only 1 known example p=93077.
2019-04-26, 13:15   #3
Brian-E

"Brian"
Jul 2007
The Netherlands

CC316 Posts

Quote:
 Originally Posted by ATH 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) ?

 2019-04-26, 13:27 #4 Dr Sardonicus     Feb 2017 Nowhere 2·3·11·59 Posts 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)).
2019-04-26, 14:05   #5
DukeBG

Mar 2018

3·43 Posts

Quote:
 Originally Posted by Brian-E 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

 2019-04-26, 14:19 #6 DukeBG   Mar 2018 3×43 Posts 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
2019-04-26, 14:20   #7
Brian-E

"Brian"
Jul 2007
The Netherlands

1100110000112 Posts

Quote:
 Originally Posted by DukeBG 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).

 2019-04-26, 14:22 #8 DukeBG   Mar 2018 3×43 Posts What do you think k is in this example? 3^4 · 11 · 757 · 93077 is not divisible by 93077^2.
2019-04-26, 14:30   #9
Brian-E

"Brian"
Jul 2007
The Netherlands

63038 Posts

Quote:
 Originally Posted by DukeBG 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?

 2019-04-26, 14:59 #10 Brian-E     "Brian" Jul 2007 The Netherlands 326710 Posts Apologies! I've totally misunderstood what k was and that led to a breakdown of communications. Ignore my posts please.
 2019-04-26, 15:03 #11 ATH Einyen     Dec 2003 Denmark 3·5·199 Posts 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