mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > Viliam Furik

Reply
 
Thread Tools
Old 2021-03-21, 15:06   #1
Viliam Furik
 
Viliam Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

10110001002 Posts
Default 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
Viliam Furik is offline   Reply With Quote
Old 2021-03-21, 15:40   #2
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

142368 Posts
Default

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.
retina is online now   Reply With Quote
Old 2021-03-21, 15:53   #3
Viliam Furik
 
Viliam Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

22×3×59 Posts
Default

Quote:
Originally Posted by retina View Post
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)
Viliam Furik is offline   Reply With Quote
Old 2021-03-21, 23:32   #4
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·3·857 Posts
Default

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
?
Dr Sardonicus is offline   Reply With Quote
Old 2021-03-22, 00:30   #5
Viliam Furik
 
Viliam Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

22·3·59 Posts
Default

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.
Viliam Furik is offline   Reply With Quote
Old 2021-03-22, 01:00   #6
slandrum
 
Jan 2021
California

111111102 Posts
Default

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.
slandrum is offline   Reply With Quote
Old 2021-03-22, 01:17   #7
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2×3×857 Posts
Default

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 is offline   Reply With Quote
Old 2021-03-22, 13:04   #8
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·3·857 Posts
Default

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.
Dr Sardonicus is offline   Reply With Quote
Old 2021-03-22, 14:41   #9
Viliam Furik
 
Viliam Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

2C416 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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.
Viliam Furik is offline   Reply With Quote
Old 2021-03-22, 15:21   #10
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

100110010100002 Posts
Default

Quote:
Originally Posted by Viliam Furik View Post
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
LaurV is offline   Reply With Quote
Old 2021-03-22, 15:24   #11
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·3·857 Posts
Default

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.
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 13:09.


Tue Dec 7 13:09:48 UTC 2021 up 137 days, 7:38, 0 users, load averages: 1.10, 1.39, 1.53

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.