- **Viliam Furik**
(*https://www.mersenneforum.org/forumdisplay.php?f=174*)

- - **Maybe useless but still interesting thing about LL sequence terms**
(*https://www.mersenneforum.org/showthread.php?t=26632*)

Maybe useless but still interesting thing about LL sequence termsI was thinking about testing Mersenne numbers, not modulo Mp but modulo p. I realized that since Mp is prime if and only if S(p-2) in LL sequence is 0 (mod Mp), then we know the S(p-2) = X * Mp, which can be expressed as S(p-2) = X * (2[SUP]p[/SUP]-1) = X*2[SUP]p[/SUP] - X. 2[SUP]p[/SUP] is 2 modulo p, according to Fermat's little theorem, thus it equals X * 2 - X = X. So S(p-2) is X modulo p.
The only problem is that I don't know how to find the value of X so that the test works properly. Is it possible to find the value of X mod p (without calculating the terms themselves)? I include a list of residues mod p for prime exponents to 67 (Mersenne prime exponents in bold): [CODE] [B]3 -> 2[/B] [B]5 -> 4[/B] [B]7-> 2[/B] 11 - > 3 [B]13 -> 12 [/B][B]17 -> 13[/B] [B]19 -> 14[/B] 23 -> 14 29 -> 21 [B]31 -> 2[/B] 37 -> 9 41 -> 37 43 -> 14 47 -> 14 53 -> 4 59 -> 14 [B]61 -> 58[/B] 67 -> 14[/CODE] |

For p = 5 I get:
s(3) = 37634 37634 mod (2^p-1) = 0 ; no surprise there 37634 = 1214 * (2^p-1) ; so X = 1214 37634 = 7526 * p + 4 So your last statement "S(p-2) is X modulo p" can't be true. X >> p and can't be a residue. |

[QUOTE=retina;574290]For p = 5 I get:
s(3) = 37634 37634 mod (2^p-1) = 0 ; no surprise there 37634 = 1214 * (2^p-1) ; so X = 1214 37634 = 7526 * p + 4 So your last statement "S(p-2) is X modulo p" can't be true. X >> p and can't be a residue.[/QUOTE] I agree it was not stated correctly. So let me correct myself: S(p-2) is congruent to X (mod p) In the case of p = 5, X is congruent to 4 (mod p), which holds, because S(p-2) is also congruent to 4 (mod p). For p = 7, the S(5) = 2,005,956,546,822,746,114 2,005,956,546,822,746,114 = 15,794,933,439,549,182 * (2 ^ p -1) 2,005,956,546,822,746,114 = 286,565,220,974,678,016 * p + 2 X = 15,794,933,439,549,182 is congruent to 2 (mod p) |

If all you want is the remainder mod p, you can speed things up a bit. The following Pari-GP code exploits the fact that S(p-2) = trace(u^(2^(p-2))) where u = Mod(x+2, x^2 - 3) is a unit or norm +1. It reproduces your results for p up to 67, but may run a bit faster than your code. The upper limit on p could be increased.
[code]? u=Mod(x+2,x^2-3);forprime(p=3,67,up=Mod(1,p)*u;m=p-kronecker(3,p);e=lift(Mod(2,m)^(p-2));t=trace(up^e);print(p" "lift(t))) 3 2 5 4 7 2 11 3 13 12 17 13 19 14 23 14 29 21 31 2 37 9 41 37 43 14 47 14 53 4 59 14 61 58 67 14 ?[/code] |

What I want is to know whether there is some rule for the value of X mod p. If we knew what would the remainder of X modulo p have to be assuming Mp is prime, then this would allow testing Mersenne numbers modulo only the exponent p.
I didn't write any script. I just made an Excel spreadsheet that calculated values of the LL sequence mod p. The "limit" of 67 is there because of practicality, and because I just didn't feel the need to go further in Excel. I don't understand the functions you used in your code. Specifically, trace and lift. I know that Kronecker exists, but I don't know what exactly it does. I could do a fairly simple code, which would do good old S(n+1) = S(n) ^ 2 - 2 (mod p), but I don't see a reason to make it. I think there may be enough data points to decide on possible patterns, and if needed, single computation for e.g. p = 521 could be enough to disprove the pattern or support it. |

I don't think you'll find out anything useful about X. Mp mod p = 1, regardless of whether Mp is prime or not. Any factor f of Mp will also have this be true: f mod p = 1.
Maybe there's something hiding there, but I suspect there isn't. |

For the purpose of calculating remainders, the recurrence (mod p) is fine. Integer modulo arithmetic is certainly faster than polynomial modulo arithmetic.
The lift function takes a specific representative of a congruence class. It replaces an intmod like Mod(1,2) by an integer; lift(Mod(1,2)) is 1. For prime p, kronecker(a, p) is 0 if a is divisible by p, +1 if a is a nonzero quadratic residue mod p, -1 if a is a quadratic non-residue mod p. If p > 3 is prime, the multiplicative order of Mod(1,p)*Mod(x+2, x^2 - 3) [that is, the multiplicative order of u = Mod(x+2, x^2 - 3) mod p] is a divisor of p - kronecker(3,p) For a = 3, p - kronecker(3,p) is m = p-1 if p == 1 or 11 (mod 12) and m = p+1 if p == 5 or 7 (mod 12). The exponent e in my script is the remainder of 2^(p-2) divided by m; Mod(2,m)^(p-2) = Mod(e,m) and e = lift(Mod(e,m)). FWIW I used the recurrence S^2 - 2 starting with Mod(4,521) to calculate S(519) mod 521 and got Mod(14,521). (If I wanted just the remainder, lift(Mod(14,521)) is 14.) |

I did notice one pattern: if p > 2 and P = 2^p - 1 is prime, then m = P - kronecker(3, P) = P + 1 = 2^p.
Now P - 2 = 2^p - 3 > p for p > 2, so Mod(2, m)^(P-2) = 0. So in this case, S(P-2) == 2 (mod P) whether 2^P - 1 is prime or not. |

[QUOTE=Dr Sardonicus;574357]I did notice one pattern: if p > 2 and P = 2^p - 1 is prime, then m = P - kronecker(3, P) = P + 1 = 2^p.
Now P - 2 = 2^p - 3 > p for p > 2, so Mod(2, m)^(P-2) = 0. So in this case, S(P-2) == 2 (mod P) whether 2^P - 1 is prime or not.[/QUOTE] I think you confuse yourself with small and big p/P. S(P-2) is of no use to anyone, because P = 2^p-1. 2^P-1 is a pretty big number... Could you please recalculate and rewrite? I think it's pointless to continue from what you wrote. Unless you are correct and I am confused and wrong. |

[QUOTE=Viliam Furik;574364]I think you confuse yourself with small and big p/P.[/QUOTE]
No, no, no, [URL="https://www.google.com/search?q=big+pp+meaning"]big PP, smol pp[/URL], never confuse them ! |

I mentioned the pattern merely because it gives examples of primes P for which S(P-2) mod P is constant (2), but S(P-2) (mod 2^P - 1) is not.
You determined that S(P-2) == 2 (mod P) for P = 3 = 2^2 - 1, 7 = 2^3 - 1, and 31 = 2^5 - 1. I checked that S(P-2) == 2 (mod P) for P = 127 = 2^7 - 1 (2^P - 1 is prime) and P = 8191 = 2^13 - 1 (2^P - 1 is composite). That got me looking for a proof that S(P-2) == 2 (mod P) when P is a Mersenne prime. The first four "double Mersennes" MMp with Mp prime are the only known prime double Mersennes. The next four, with p = 13, 17, 19, and 31 are known to be composite because proper factors have been found. S(P-2) == 2 (mod P) and S(P-2) == 0 (mod 2^P - 1) for P = 2^2 - 1, 2^3 - 1, 2^5 - 1, and 2^7 - 1. I know that S(8189) == 2 (mod 8191). I don't know what S(8189) (mod 2^8191 - 1) is, but I do know it isn't 0. Likewise for P = 2^17 - 1, 2^19 - 1, and 2^31 - 1. |

All times are UTC. The time now is 03:33. |

Powered by vBulletin® Version 3.8.11

Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.