20210321, 15:06  #1 
"Viliam Furík"
Jul 2018
Martin, Slovakia
680_{10} 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(p2) in LL sequence is 0 (mod Mp), then we know the S(p2) = X * Mp, which can be expressed as S(p2) = X * (2^{p}1) = X*2^{p}  X. 2^{p} is 2 modulo p, according to Fermat's little theorem, thus it equals X * 2  X = X. So S(p2) 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 
20210321, 15:40  #2 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2^{2}·1,571 Posts 
For p = 5 I get:
s(3) = 37634 37634 mod (2^p1) = 0 ; no surprise there 37634 = 1214 * (2^p1) ; so X = 1214 37634 = 7526 * p + 4 So your last statement "S(p2) is X modulo p" can't be true. X >> p and can't be a residue. 
20210321, 15:53  #3  
"Viliam Furík"
Jul 2018
Martin, Slovakia
680_{10} Posts 
Quote:
S(p2) is congruent to X (mod p) In the case of p = 5, X is congruent to 4 (mod p), which holds, because S(p2) 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) 

20210321, 23:32  #4 
Feb 2017
Nowhere
2^{2}·29·43 Posts 
If all you want is the remainder mod p, you can speed things up a bit. The following PariGP code exploits the fact that S(p2) = trace(u^(2^(p2))) 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^23);forprime(p=3,67,up=Mod(1,p)*u;m=pkronecker(3,p);e=lift(Mod(2,m)^(p2));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 ? 
20210322, 00:30  #5 
"Viliam Furík"
Jul 2018
Martin, Slovakia
2^{3}·5·17 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. 
20210322, 01:00  #6 
Jan 2021
California
11011100_{2} 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. 
20210322, 01:17  #7 
Feb 2017
Nowhere
1001101111100_{2} 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 nonresidue 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 = p1 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^(p2) divided by m; Mod(2,m)^(p2) = 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.) 
20210322, 13:04  #8 
Feb 2017
Nowhere
11574_{8} 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)^(P2) = 0. So in this case, S(P2) == 2 (mod P) whether 2^P  1 is prime or not. 
20210322, 14:41  #9  
"Viliam Furík"
Jul 2018
Martin, Slovakia
2^{3}·5·17 Posts 
Quote:
S(P2) is of no use to anyone, because P = 2^p1. 2^P1 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. 

20210322, 15:21  #10 
Romulan Interpreter
Jun 2011
Thailand
9786_{10} Posts 
No, no, no, big PP, smol pp, never confuse them !
Last fiddled with by LaurV on 20210322 at 15:22 
20210322, 15:24  #11 
Feb 2017
Nowhere
4988_{10} Posts 
I mentioned the pattern merely because it gives examples of primes P for which S(P2) mod P is constant (2), but S(P2) (mod 2^P  1) is not.
You determined that S(P2) == 2 (mod P) for P = 3 = 2^2  1, 7 = 2^3  1, and 31 = 2^5  1. I checked that S(P2) == 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(P2) == 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(P2) == 2 (mod P) and S(P2) == 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  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Factordb and aliquot sequences with useless size terms  garambois  Aliquot Sequences  10  20170902 00:21 
not exactly in laymans terms, but interesting Riemann site  Fusion_power  Lounge  0  20130927 17:52 
Lucaslike sequence of polynomials: a tricky thing  XYYXF  Math  7  20100827 11:52 
A new interesting thing about 15k  robert44444uk  15k Search  0  20050406 23:00 
Useless p1 work  jocelynl  Data  4  20041128 13:28 