Possible values for k (in Mersenne factors)

[James Heinrich]

I'm trying to figure out the pattern behind what values of k are acceptable for Mersenne factors in the form 2kp+1.

The mersenne.org math page simply says:

One very nice property of Mersenne numbers is that any factor q of 2P-1 must be of the form 2kp+1. Furthermore, q must be 1 or 7 mod 8. A proof is available. Finally, an efficient program can take advantage of the fact that any potential factor q must be prime.

This mentions constraints on factor q, but not on k.

Running through a list of known factors shows that certain values of k just aren't viable, but the pattern is not obvious to me. For example, the first 100 possible values of k are (with blank lines left indicating impossible values):

1

3
4
5

7
8
9

11
12
13

15
16
17

19
20
21

23
24
25

27
28
29

31
32
33

35
36
37

39
40
41

43
44
45

47
48
49

51
52
53

55
56
57

59
60
61

63
64
65

67
68
69

71
72
73

75
76
77

79
80
81

83
84
85

87
88
89

91
92
93

95
96
97

99
100
101

103
104
105

107
108
109

111
112
113

115
116
117

119
120
121

123
124
125

127
128
129

131
132

The only patterns I see (whether real or imagined):

• all values of 2*<single prime factor> (e.g. 6, 10, 14, 22, 26, 34) are not-acceptable
• all prime values (except 2) are acceptable.
• all powers of a single prime (4,8,16,32,64,128; 3,9,27,81) are acceptable

But that doesn't explain 18,30,42,50

What are the rules governing which values of k are acceptable?


edit: Actually, looking again at the list I now see the obvious triplet-grouping: every 4th number is skipped. Is that it?

[science_man_88]

since primes>3 are 1 or 5 mod 6 we can reduce to:

2*k*p+1 = 1 or 5 mod 6 plug in p=p mod 6 and solve for k they will fall in certain classes same with moduli like 120. you can find out things from these.

[James Heinrich]

Originally Posted by science_man_88

2*k*p+1 = 1 or 5 mod 6 plug in p=p mod 6 and solve for k they will fall in certain classes same with moduli like 120. you can find out things from these.

I understood none of what you said, unfortunately.

Please use very simple words in explaining this to me (yes, I know I don't belong in the math forum).

So far (k % 4) != 2 seems to hold up against my list of known k values, but I'm not sure if this simple observation is sufficient to determine what k values are acceptable?

Originally Posted by science_man_88

this has been discussed before but:

? for(x=1,120,if(gcd(x,120)==1 && (x%8==7 || x%8==1),print1(x",")))
1,7,17,23,31,41,47,49,71,73,79,89,97,103,113,119,

I'm also not sure what this has to do with k values?

[science_man_88]

Originally Posted by James Heinrich

I understood none of what you said, unfortunately.

Please use very simple words in explaining this to me (yes, I know I don't belong in the math forum).

So far (k % 4) != 2 seems to hold up against my list of known k values, but I'm not sure if this simple observation is sufficient to determine what k values are acceptable?

I'm also not sure what this has to do with k values?

the values of k mod a modulus depend on p mod the modulus because given that and the values a prime can take on mod that modulus 2*k*p+1 can be solved down to possible values of k:

example:

p=1 mod 6

2*k*p+1 since p=p mod 6 will work we get 2*k*1+1 = 2*k+1 = either 1 or 5 mod 6, k=2 gives you 5 mod 6 and so will increasing k by 3 since 2*3 = 6 so k=2 mod 3 for p=1 mod 6 and 2*k*p+1 = 5 mod 6, what if 2*k*p+1 is 1 mod 6 and p = 1 mod 6 once again 2*k*1+1 = 2*k+1 okay so k=0 works , once again repeating every 3 so k=0 mod 3 so for p= 1 mod 6, k=0 or 2 mod 3 .

[science_man_88]

Originally Posted by James Heinrich

I'm also not sure what this has to do with k values?

what these have to do with k values in 2*k*p+1 is that these are the values mod 120 that fit being able to be prime and 1 or 7 mod 8, which are the values mod 120, 2*k*p+1 must take on. as shown with mod 6 this can be backtracked to possible k mod 120 values.

[James Heinrich]

Perhaps I can understand code better than words.

If I understand you correctly, whether or not a certain k is viable depends on p? Can you show me some example code (C, PARI, PHP, pseudo, whatever) that will determine if k is appropriate for any give p?

Taking a specific example, how would I determine which values of k<50 are valid for M39183121 (chosen at random but with known factors for k=3,8,48):

p=39183121; for(k=1, 50, if(<something to determine if k is viable>, print(k)););

[rcv]

Originally Posted by James Heinrich

Perhaps I can understand code better than words.

James:

The following are from the comments in my gpusieve.cu code, which is released under GPL, and which is in a BDot source archive, somewhere.

The last two lines cut to the chase. The first couple of dozen lines explain "why".

//     Furthermore, all candidates must be equal to 1 or 7,
//     modulo 8 to be a factor of a Mersenne number.  This lets
//     us reduce by another factor of 2 the work we might
//     otherwise have performed.  [It might appear we should be
//     reducing the work by a factor of 4, but we are inherently
//     only considering odd candidates, so we can only
//     eliminate candidates that are equal to 3 or 5, modulo 8.]
//
//     By theorem, all factors of a mersenne number are of the
//     form, 2*k*p+1, where k is a positive integer and p is the
//     exponent of the Mersenne number.
//
//     The following table contains (2*k*p) mod 8 for each
//     possible combination of a k-value with an odd Mersenne exponent.
//
//                   (2*k) mod 8
//       p mod 8   0   -   2   -   4   -   6   -
//                -------------------------------
//          1   |  0   -   2   -   4   -   6   -
//          3   |  0   -   6   -   4   -   2   -
//          5   |  0   -   2   -   4   -   6   -
//          7   |  0   -   6   -   4   -   2   -
//
//     Next, we look at the candidates (2*k*p+1) mod 8.  The valid
//     candidates are equal to 1 or 7.  Others need not be generated.
//
//                   (2*k) mod 8
//       p mod 8   0   1   2   3   4   5   6   7
//                -------------------------------
//          1   |  1   -   -   -   -   -   7   -
//          3   |  1   -   7   -   -   -   -   -
//          5   |  1   -   -   -   -   -   7   -
//          7   |  1   -   7   -   -   -   -   -
//
//     This shows us that if (p mod 4) == 1, then k must equal 0 or 3 (modulo 4).
//                    and if (p mod 4) == 3, then k must equal 0 or 1 (modulo 4).

[science_man_88]

Originally Posted by James Heinrich

Perhaps I can understand code better than words.

If I understand you correctly, whether or not a certain k is viable depends on p? Can you show me some example code (C, PARI, PHP, pseudo, whatever) that will determine if k is appropriate for any give p?

Taking a specific example, how would I determine which values of k<50 are valid for M39183121 (chosen at random but with known factors for k=3,8,48):

p=39183121; for(k=1, 50, if(<something to determine if k is viable>, print(k)););

? p=39183121; for(k=1, 50, if((2*k*p+1)%6==1 || (2*k*p+1)%6==5, print(k","k%3)););
2,2
3,0
5,2
6,0
8,2
9,0
11,2
12,0
14,2
15,0
17,2
18,0
20,2
21,0
23,2
24,0
26,2
27,0
29,2
30,0
32,2
33,0
35,2
36,0
38,2
39,0
41,2
42,0
44,2
45,0
47,2
48,0
50,2

I checked if 2*k*p+1 was 1 or 5 mod 6 if so k is a possibility for p in this case, it's shown they are all 0 or 2 mod 3.


moving on they can only work if 2*k*p+1 is 1 or 7 mod 8:

? p=39183121; for(k=1, 50, if(((2*k*p+1)%6==1 || (2*k*p+1)%6==5) && ((2*k*p+1)%8==1 || (2*k*p+1)%8==7), print(k)););
3
8
11
12
15
20
23
24
27
32
35
36
39
44
47
48

these k survive when that condition is met we could of figured out when the mod groups crossed mod another number but I left it simple.

[LaurV]

As an addition to what was said, this is exactly what mfakt* is doing with those classes.
(1.) If a factor is 2*k*p+1 AND 8*x+1, then you solve the system in integers and get that the factor is in fact 8*h*p+1, for any h. That is, k=4h, i.e. k=0 (mod 4).
(2.) If a factor is 2*k*p+1 AND 8*x-1, then you solve the system in integers, but this time you get two solutions, dependent on p:
(2.a.) For p=4*t+3, (i.e. p=3 mod 4) the factor is 8*h*p+2*p+1. That is, k=(4*h+1), i.e. k=1 (mod 4).
(2.b.) For p=4*t+1, (i.e. p=1 mod 4) the factor is 8*h*p+6*p+1. That is, k=(4h+3), i.e. k=3 (mod 4).

This automatically eliminates all the candidates which are 3 or 5 (mod 8).

Only this in itself would be enough to filter the values of k quite a lot. For example, as your 39183121 is 1 (mod 4), it can have only factors of the form (1) and (2b). This already filters the values of k to a half, like 3, 4, 7, 8, 11, 12, 15, 16, etc.

Adding to this the fact that the factors are prime: we can consider the first primorial, 6, and say the factors must be 1 or 5 mod 6, you already make a lot of progress, about another quarter of the remaining candidates are gone.

In fact, 12 would be a better choice then 6, because is divisible by 4, and remember, k has a nice modularity with 4. It is essential that the modulus be multiple of 4. Anyhow you will reach this after calculus, if you want to eliminate the candidates which are 3 or 5 mod 8. If you take 12, a candidate can be prime only if it is 1, 5, 7, 11 (mod 12), but the 5 and 11 (mod 12) may be (or may be not, depending on p) 5 or 3 mod 8, so they are not wanted from the start. For different p, other two classes may not be wanted, but two classes will ALWAYS be eliminated from the start.

In fact, 6 has nothing magic in it, it is just the first primorial.

A much better way is to consider a larger primorial, multiplied by two, for example 2*(2*3*5*7*11). If you compute this, it is 4620, and now you get to mfakt* and to where the number of classes come from.

As Oliver explained so many times, those are modularity classes for k in expression q=2*k*p+1. For this expression to be prime, to be 1 or 7 (mod 8) the classes of k are highly dependent of the classes of p. For example, for the chosen number p=39183121, which is 1 (mod 4) and 901 (mod 4620):

- k can not be 1 (mod 4620). In this case q will be 2*901+1=1803 (mod 4620) which is not prime (divisible by 3). And so on for the classes of modularity 1, 4, 7, 10, +3 +3 etc). This eliminates a third of the classes.
- k can not be 2 (mod 4620) - this is divisible by 5. And same for classes 2, 7, 12, 17, +5, +5 ...

- etc.

This is much like the Eratosthenes' sieve, but applied to 4620 numbers only. Once you get this class is divisible by 3, all +3 are divisible by 3. If this class is divisible by 11, all +11 classes are divisible by 11.

[edit: also, if a for a k we have 2*k*p+1 is 3 or 5 (mod 8), then 2*(k+4620)*p+1 will also be 3 or 5 (mod 8), so once you eliminated a class, you don't need to care about it during sieving process, whole class is safely eliminated, there will be no 3 or 5 (mod 8) numbers in the sieve - see below]

At the end, a lot of classes are eliminated because they can't result in prime numbers. The 3 or 5 mod 8 are eliminated "by construction". All this process takes a blink of an eye and if you start mfactc on this number you will see that it starts testing only the classes 0, 3, 8, 11, 15, 20, 24, 35, 36, etc, only the classes which are blue in the attached table.


Only 960 classes survive the "filtering". It does not seem to be very regulated, but the process itself is a very deterministic :D

For example in class 3 there will be k of the form:

3,
3+4620,
3+2*4620,
3+3*4620,
.....
etc,

resulting in corespondent factor-candidates of the form

2*3*39183121+1,
2*(3+4620)*39183121+1,
2*(3+2*4620)*39183121+1,
2*(3+3*4620)*39183121+1,
2*(3+4*4620)*39183121+1,
...
etc.

The candidates of the form 2*(k+n*4620)*p+1, with all k in the 960 remaining classes and natural n, are the only candidates having the chance to be prime, and to be 1 or 7 mod 8. Other numbers with k in different classes CANNOT be factors of Mp (they are either not prime, or not 1,7 mod 8). More then this you can't dig.

Further on, the candidates in each class have to be sieved with small primes (done by CPU) and only the surviving will be used for modular exponentiation to test if 2^39183121=1 mod each survivor (done by GPU).

That is one of the reasons why mfaktc is so efficient.

[LaurV]

[time limit still editing it every 5 minutes :D. Now I am trying to change the ending, as I did some calculus meantime:]

[discussion was related to class k=3, modified example to n=10]

resulting in corespondent factor-candidates of the form

2*3*39183121+1 = 235098727
2*(3+4620)*39183121+1 = 362287136767
2*(3+2*4620)*39183121+1 = 724339174807
2*(3+3*4620)*39183121+1 = 1086391212847
2*(3+4*4620)*39183121+1 = 1448443250887
2*(3+5*4620)*39183121+1 = 1810495288927
2*(3+6*4620)*39183121+1 = 2172547326967
2*(3+7*4620)*39183121+1 = 2534599365007
2*(3+8*4620)*39183121+1 = 2896651403047
2*(3+9*4620)*39183121+1 = 3258703441087
2*(3+10*4620)*39183121+1 = 3620755479127
...
etc.

<snip see the post above >

In the example above, sieving the class k=3 with primes up to 10000 will eliminate all the candidates, except for n=0,3,6,8. Remark that only candidates for n=0,6 are prime (marked in bold), but we don't know this, and deciding their primality is more costly then doing exponentiation.

[ATH]

If you look at a specific exponent p then there is lots of k values which cannot result in a mersenne factor q=2kp+1.

But if you look at a specific k value and ask if there is any mersenne number 2^p-1 which has the factor q=2kp+1 then the only k-values that does not correspond to a factor is those with k=2 (mod 4).

This comes from q has to be 1 or 7 (mod 8). Prime p>2 is equal to 1,3,5,7 (mod 8), so 2*p is 2 or 6 (mod 8), and for k=2,6 (mod 8): 2kp+1 is always 5 (mod 8).

Looking at the 16 possible values for q (mod 120) does not give any further restriction on k.