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.

All times are UTC. The time now is 18:30.