Maybe useless but still interesting thing about LL sequence terms

Viliam Furik · 2021-03-21, 15:06

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 * (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(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

retina · 2021-03-21, 15:40

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.

Viliam Furik · 2021-03-21, 15:53

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)

Dr Sardonicus · 2021-03-21, 23:32

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
?

Viliam Furik · 2021-03-22, 00:30

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.

slandrum · 2021-03-22, 01:00

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.

Dr Sardonicus · 2021-03-22, 01:17

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.)

Dr Sardonicus · 2021-03-22, 13:04

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.

Viliam Furik · 2021-03-22, 14:41

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.

LaurV · 2021-03-22, 15:21

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 !

Dr Sardonicus · 2021-03-22, 15:24

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.

2021-03-21, 15:06	#1
Viliam Furik "Viliam Furík" Jul 2018 Martin, Slovakia 1430₈ 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 * (2^p-1) = X2^p - X. 2^p 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, 23:32	#4
Dr Sardonicus Feb 2017 Nowhere 1842₁₆ 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 ?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Factordb and aliquot sequences with useless size terms	garambois	Aliquot Sequences	10	2017-09-02 00:21
not exactly in laymans terms, but interesting Riemann site	Fusion_power	Lounge	0	2013-09-27 17:52
Lucas-like sequence of polynomials: a tricky thing	XYYXF	Math	7	2010-08-27 11:52
A new interesting thing about 15k	robert44444uk	15k Search	0	2005-04-06 23:00
Useless p-1 work	jocelynl	Data	4	2004-11-28 13:28

2021-03-21, 15:40	#2
retina Undefined "The unspeakable one" Jun 2006 My evil lair 2×3²×7×53 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-22, 00:30	#5
Viliam Furik "Viliam Furík" Jul 2018 Martin, Slovakia 1430₈ 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 11·47 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³×5×23 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 1100001000010₂ 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, 15:24	#11
Dr Sardonicus Feb 2017 Nowhere 2×3³×5×23 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.