 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 10111010012 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 22×3×17×31 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

5×149 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 2·3·7·127 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 5×149 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 22×3×52 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 2·3·7·127 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 123268 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

5·149 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

268316 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 14D616 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.   Thread Tools Show Printable Version Email this Page 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 00:58.

Mon Jan 17 00:58:46 UTC 2022 up 177 days, 19:27, 0 users, load averages: 1.15, 1.19, 1.21