mersenneforum.org (https://www.mersenneforum.org/index.php)
-   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)

 Viliam Furik 2021-03-21 15:06

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[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]

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

 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
?[/code]

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

 LaurV 2021-03-22 15:21

[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 !

 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.

 Viliam Furik 2021-03-22 17:12

[QUOTE=LaurV;574368]No, no, no, [URL="https://www.google.com/search?q=big+pp+meaning"]big PP, smol pp[/URL], never confuse them ![/QUOTE]

:jokedrum:

Good one. :D

 Viliam Furik 2021-03-22 17:18

The pattern you observed is fairly trivial I would say. If the prime exponent you're testing modulo p is itself a Mersenne prime, then you are testing the Mersenne prime with a smaller exponent. For all Mersenne primes, S(x) (for x >= p) is equal to 2, because S(p-2) = 0 (mod p), S(p-1) = -2 (mod p), and S(p) = 2 (mod p).

So if there can be such a test for Mersenne numbers modulo p, it won't work for double Mersennes.

 Dr Sardonicus 2021-03-23 12:39

The fact that S(P-2) mod p doesn't tell you anything about whether 2^P - 1 may be prime when P = 2^p - 1 is prime, disproves the existence of a general "S(p-2) mod p" test for Mersenne primes.

More important than this specific case IMO is the fact that S(p-2) == trace(u^e) (mod p), where u = Mod(x+2,x^2 - 3) and e = 2^(p-2)%m, where

m = p - 1 if p == 1 or 11 (mod 12)

m = p + 1 if p == 5 or 7 (mod 12).

We know that u^m == 1 (mod p) so the exact multiplicative order of u (mod p) is a divisor of m. I have not investigated when it might be known to be a [i]proper[/i] divisor.

If there were some pattern in S(p-2) (mod p) that indicated whether 2^p - 1 was prime, presumably it would somehow be manifest in the "reduced" exponent e = 2^(p-2)%m. I am not aware of any convenient formula for this remainder, but I don't know that there isn't one.

So far the "trivial" pattern when p is a Mersenne prime is the only consistent one I am aware of, and in that case S(p-2) mod p utterly fails to indicate whether 2^p - 1 is prime.

 Viliam Furik 2021-04-11 16:06

Update

I have been trying to find something and came across the Wikipedia page for the LL test, where it says, that the sign of the S(p-3) is (-1)[SUP](p-1)/2[/SUP] (except for p = 5), for starting value of 2/3, which is the Wagstaff number with exponent p, i.e. (2[SUP]p[/SUP]+1)/3. This turns out to be 1 (mod p). Thus LL test with starting value of 2/3, and done modulo p is entirely composed of terms p-1, always. Using the property of the sign I tried to devise a checking test which under the assumption of the Mp being prime checks whether the conditions fit according to the known sign of the S(p-3).

S(p-2) = X * (2[SUP]p[/SUP]-1)
S(p-2) = X (mod p)

S(p-3) = K * (2[SUP]p[/SUP]-1) + sign * 2[SUP](p+1)/2[/SUP]
S(p-3) = K + sign * 2[SUP](p+1)/2[/SUP] (mod p)

S(p-2) = S(p-3)[SUP]2[/SUP] - 2 = K[SUP]2[/SUP] + sigma * 2 * K * 2[SUP](p+1)/2[/SUP] + 2[SUP]p+1[/SUP] - 2 = K[SUP]2[/SUP] + sigma * K * 2[SUP](p+3)/2[/SUP] + 2 = K(K + sigma * 2[SUP](p+3)/2[/SUP]) + 2

using the property that all terms after the first one are -1 (mod p)

S(p-2) = S(p-3) = -1 (mod p)
S(p-2) = K(K + sigma * 2[SUP](p+3)/2[/SUP]) + 2 = -1 (mod p)
K(K + sigma * 2[SUP](p+3)/2[/SUP]) = -3 (mod p)

I observed that for all primes the 2[SUP](p+3)/2[/SUP] is either 4 or -4 (mod p). I later realised that it's because 2[SUP]p+3[/SUP] is 16 (mod p), or equivalent if p < 16, thus the square root of 16 is 4 or -4. This means that the equation becomes

K(K +- 4) = -3 (mod p)

For the plus case, the solutions for K are -3 and -1, of which only -3 seems to satisfy the condition from the fourth row. For the minus case, the solutions are 1 and 3, and again, only 1 seems to ever satisfy the condition.

That would all be nice unless ALL primes p satisfied these conditions, which they do.

Is there any other way to modify this, so that we can use this test at all, or does it mean something in the sense of all Mersenne numbers being something like PRP modulo p (thus signifying impossibility of such test)?

I also tried something with starting value 4, and 10, because there is a relation between signs of S(p-3) for these starting values, but it only gives the product of the signs.

 All times are UTC. The time now is 22:56.