mersenneforum.org Maybe useless but still interesting thing about LL sequence terms
 Register FAQ Search Today's Posts Mark Forums Read

 2021-03-21, 15:06 #1 Viliam Furik     "Viliam Furík" Jul 2018 Martin, Slovakia 2×373 Posts Maybe useless but still interesting thing about LL sequence terms I 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 * (2p-1) = X*2p - X. 2p 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: 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
 2021-03-21, 15:40 #2 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 2·3,167 Posts 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.
2021-03-21, 15:53   #3
Viliam Furik

"Viliam Furík"
Jul 2018
Martin, Slovakia

2×373 Posts

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

 2021-03-21, 23:32 #4 Dr Sardonicus     Feb 2017 Nowhere 7×13×59 Posts 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 ?
 2021-03-22, 00:30 #5 Viliam Furik     "Viliam Furík" Jul 2018 Martin, Slovakia 2·373 Posts 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.
 2021-03-22, 01:00 #6 slandrum   Jan 2021 California 24·19 Posts 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.
 2021-03-22, 01:17 #7 Dr Sardonicus     Feb 2017 Nowhere 7×13×59 Posts 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.)
 2021-03-22, 13:04 #8 Dr Sardonicus     Feb 2017 Nowhere 123718 Posts 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.
2021-03-22, 14:41   #9
Viliam Furik

"Viliam Furík"
Jul 2018
Martin, Slovakia

2·373 Posts

Quote:
 Originally Posted by Dr Sardonicus 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.
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.

2021-03-22, 15:21   #10
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

987010 Posts

Quote:
 Originally Posted by Viliam Furik I think you confuse yourself with small and big p/P.
No, no, no, big PP, smol pp, never confuse them !

Last fiddled with by LaurV on 2021-03-22 at 15:22

 2021-03-22, 15:24 #11 Dr Sardonicus     Feb 2017 Nowhere 14F916 Posts 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post garambois Aliquot Sequences 10 2017-09-02 00:21 Fusion_power Lounge 0 2013-09-27 17:52 XYYXF Math 7 2010-08-27 11:52 robert44444uk 15k Search 0 2005-04-06 23:00 jocelynl Data 4 2004-11-28 13:28

All times are UTC. The time now is 07:52.

Tue Jan 25 07:52:38 UTC 2022 up 186 days, 2:21, 0 users, load averages: 1.06, 1.25, 1.19