mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Prime Gap Searches

Reply
 
Thread Tools
Old 2020-01-18, 11:50   #1
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

22×7×19 Posts
Default Patterns in primes that are primitive roots / Gaps in full-reptend primes

This started out as a search for gaps between cyclic or full-reptend primes, where 10 is a primitive root mod p (A001913):
Code:
gap  p
  2  17
  4  19
  6  23
  8  491
 10  7
 12  47
 14  419
 16  577
 18  29
 20  -
 22  1789
...  ...
A gap of 20 seemed impossible to find. And indeed, gaps that are congruent to 20 (mod 40) are not admissible.
If 10 is not a square mod p and p-20 or p+20 is a prime, then 10 is a square mod p-20 or p+20 respectively.

In general, for primes p where r is a primitive root mod p, these gaps are all inadmissible:
Code:
 r  gaps congruent to
 2  4 (mod 8)
 3  4,6,8 (mod 12)
 5  2,8 (mod 10)
 6  8,12,16 (mod 24)
 7  14 (mod 28)
 8  2,4,8,10,12,14,16,20,22 (mod 24)
10  20 (mod 40)
11  22 (mod 44)
12  4,6,8 (mod 12)
13  none
14  28 (mod 56)
15  20,30,40 (mod 60)
17  none
18  4 (mod 8)
19  38 (mod 76)
20  2,8 (mod 10)
I have a vague idea that this can be checked via the Legendre or Jacobi symbol and that (\frac{r}{p})=(-1)^{\frac{(r-1)(p-1)}{4}}(\frac{p}{r}), but I'm kind of stuck here (especially when r is not prime). Would like to understand how to prove it, as it would also help to determine that 11 is the smallest number that can be a primitive root mod every prime of a prime quadruplet p+{0,2,6,8}, a result I stumbled upon several years ago.


Next, looking for record gaps between Wieferich primes...
Attached Files
File Type: txt FRP gaps.txt (7.6 KB, 27 views)

Last fiddled with by mart_r on 2020-01-18 at 11:56
mart_r is offline   Reply With Quote
Old 2020-01-18, 15:47   #2
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

CB216 Posts
Default

Quote:
Originally Posted by mart_r View Post
<snip>
I have a vague idea that this can be checked via the Legendre or Jacobi symbol and that (\frac{r}{p})=(-1)^{\frac{(r-1)(p-1)}{4}}(\frac{p}{r}), but I'm kind of stuck here (especially when r is not prime). Would like to understand how to prove it, as it would also help to determine that 11 is the smallest number that can be a primitive root mod every prime of a prime quadruplet p+{0,2,6,8}, a result I stumbled upon several years ago.
<snip>
I assume r is a positive integer. Let r = d*f^2 where d is square free (in Pari-GP, d = core(r)). If d = 1, r is a perfect square. Bail out! Otherwise...

If d is not congruent to 1 (mod 4), d = 4*d.

Now, d is a "fundamental discriminant," and (apart from primes that may have divided r to even powers), is the least modulus for which the quadratic character (r/p) is equal to (p/d). Whether d is a quadratic residue (mod p) depends only on p (mod d).

Thus, the quadratic character of r (mod p) is (again, apart from primes p that divide r to even powers) equal to (p/d).

For example, if r = 10, we obtain d = 40.

You can compute the quadratic non-residues (mod d) [assuming d isn't very big] in Pari-GP as follows:

Code:
v=vector(eulerphi(d)/2);j=0;for(i=1,d-1,if(kronecker(i,d)==-1,j++;v[j]=i))
Since d is even, the values in v are all odd, so the differences between any two of them are even.

But things get a bit tricky. If the odd part of d is congruent to 1 (mod 4), then if k is one of the numbers in v, so is d - k. Thus, the differences v[j] - v[i] for j > i will give all possible gaps between quadratic non-residues (mod d).

However, if the odd part of d is congruent to 3 (mod 4) this may not be true. (It happens to be true for d = 4*3 = 12, where v = [5, 11] and the only difference is 6). I checked the cases d = 4*7 and 4*11, and in both cases the further differences d + v[i] - v[j] for j > i gave all the even gaps (mod d) that weren't given by v[j] - v[i] with j > i. For r = 11, d = 44, here are the results:

Code:
? d=44;v = vector(eulerphi(d)/2);j=0;for(i=1,d-1,if(kronecker(i,d)==-1,j++;v[j]=i))

? w=vector(#v*(#v-1));k=0;for(i=1,#v-1,for(j=i+1,#v,m=v[j]-v[i];k++;w[k]=m;m=d-m;k++;w[k]=m));w=vecsort(w);

? w
%3 = [2, 2, 2, 2, 4, 4, 4, 4, 6, 6, 6, 6, 8, 8, 8, 8, 10, 10, 10, 10, 12, 12, 12, 12, 14, 14, 14, 14, 16, 16, 16, 16, 18, 18, 18, 18, 20, 20, 20, 20, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 24, 24, 24, 24, 26, 26, 26, 26, 28, 28, 28, 28, 30, 30, 30, 30, 32, 32, 32, 32, 34, 34, 34, 34, 36, 36, 36, 36, 38, 38, 38, 38, 40, 40, 40, 40, 42, 42, 42, 42]

I suspect the general result is known, but I am too lazy to track it down at the moment.
Dr Sardonicus is offline   Reply With Quote
Old 2020-01-18, 22:16   #3
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

62628 Posts
Default

Oh, boy, did I ever foul up!


I did the wrong kronecker() calculation. I should have put the value of d first.

So I started over, and cobbled together something that at least gives results. I'm sure it could be turned into something usable for at least very small values of interest.

The following Pari-GP code does work, but it is a total kludge. I wouldn't use it on numbers d of any size. I didn't even bother with code to make the value of d "suitable," which I decided was values that were either 4 or 8 times odd square free numbers. Given a value r, d = 4*core(r).

Instead, I stuck to code for a specific value of d while I worked out my other mistakes, and when I got something that actually worked, tried other values of d by recalling the previous command and filling in new values by hand.

I found that for d = 4*3, the gaps 4, 6, and 8 did not occur as the differences of non-residues. For d = 4*5, the gaps 2, 8, 12, and 18 do not occur. d = 4*p, p = 13, 17, and 29, all gaps occur as differences of non-residues. For d = 4*p, p = 7, 11, 19, and 23, only the gap 2*p does not occur.

For d = 8*3, the gaps 8, 12, and 16 do not occur. For d = 8*p, p = 5, 7, 11, 13, 17, 19, only the gap 4*p does not occur.

Code:
{
d=120;
v=vector(eulerphi(d)/2);
j=0;
for(i=1,d-1,if(kronecker(d,i)==-1,j++;v[j]=i));
w=vector(#v*(#v-1));
k=0;
for(i=1,#v-1,for(j=i+1,#v,k++;w[k]=v[j]-v[i];k++;w[k]=d+v[i]-v[j]));
gaplist=listsort(List(w),1);
if(#gaplist==d/2-1,
print();
print("For d = "d" all gaps occur");
return(),
l=d/2-#gaplist-1;
ng=vector(l);
g=vector(d/2-1,i,2*i);
for(i=1,#gaplist,
r=gaplist[i];
g[r/2]=0
);
j=0;
for(i=1,d/2-1,
if(g[i]>0,
j++;
ng[j]=g[i])
);
);
print();
print("d = "d);
print("Vector of gaps that are not differences of non-residues is "ng)
}
The output is

d = 120
Vector of gaps that are not differences of non-residues is [40, 60, 80]
Dr Sardonicus is offline   Reply With Quote
Old 2020-01-19, 14:28   #4
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

22·7·19 Posts
Default

Thanks, that helps a lot!

Based on your first post, I wrote my own program, and the results agree with yours. At first I was a bit confused about the results for r=8, but since 8 is a perfect power it's a slightly different story where kronecker alone doesn't help. (All primitive roots mod 8 are either 3, 5, or 11 mod 24.)

I can't say that I fully understand all the maths behind it yet, but I can relate to the following:

A non-perfect power r can only be a primitive root mod p if it's not a square mod (p mod 4r). Thus, to check which gaps are inadmissible, we only have to check all the differences between the set of odd numbers 2n+1 < 8r for which r is a nonsquare mod 2n+1.

That, in principle, answers my main questions about this subject.
But I'm going to work my way through the proof of quadratic reciprocity once more. I'm reading "Elementary Number Theory" by W. Stein.
mart_r is offline   Reply With Quote
Old 2020-01-19, 14:43   #5
sweety439
 
sweety439's Avatar
 
Nov 2016

22·13·37 Posts
Default

For gaps between primes p which 2 is primitive root mod p:

Code:
2,3
6,5
8,29
10,19
14,149
16,37
18,83
22,421
24,107
26,587
30,317
32,2099
34,619
38,2621
40,1693
42,227
46,1381
48,709
50,3203
54,2477
56,4547
58,12979
62,4157
64,4723
66,1307
70,4021
72,947
74,1787
78,5573
80,12659
82,23251
86,20357
88,9949
90,13523
94,18493
96,15971
98,14243
102,33637
104,3083
106,63667
110,20789
112,24547
114,9059
118,88093
120,11317
122,109619
126,70717
128,46349
130,49891
134,244109
136,70237
138,105691
142,132709
144,18269
146,425387
150,221261
152,266117
154,62323
158,235541
160,31699
162,139907
166,102877
168,65371
170,142211
174,199037
176,265163
178,296299
182,223829
184,411013
186,137723
190,699757
192,191837
194,658643
198,103093
200,339827
202,302227
206,2989757
208,806581
210,425603
214,155797
216,598427
218,184259
222,736469
224,514949
226,2373307
230,1530293
232,1078411
234,512819
238,1427509
240,370133
242,1353371
246,2084653
248,476603
250,2551099
254,4013573
256,2617651
A more generalization: gaps of primes p such that znorder(Mod(b,p)) = (p-1)/a, for fixed integers a>=1, b>=2 (for some (a,b) pairs such primes do not exist, e.g. (4,3) and (5,5)).
sweety439 is offline   Reply With Quote
Old 2020-01-19, 14:49   #6
sweety439
 
sweety439's Avatar
 
Nov 2016

22·13·37 Posts
Default

This is a list of the primes p such that p+2 is also prime, and both p and p+2 have primitive root 2:

3, 11, 59, 179, 347, 419, 659, 827, 1451, 1619, 1667, 2027, 2267, 3467, 3851, 4019, 4091, 4259, 4787, 6779, 6827, 6947, 7547, 8219, 8291, 8819, 9419, 10067, 10091, 10139, 10499, 10859, 12251, 12611, 13931, 14387, 14627, 14867, 16067, 16187, 16979, 17387, 17747, 19139, 20507, 20771, 21011, 21491, 21587, 21611, 22619, 22859, 23027, 23627, 24107, 25931, 27059, 28307, 28547, 28571, 29387, 30011, 30467, 30851, 32027, 32531, 32939, 33347, 33827, 34211, 34259, 35051, 35507, 36011, 36107, 36467, 36779, 36899, 37547, 38651, 38747, 39227, 44267, 44531, 44699, 45587, 46091, 46307, 47147, 47387, 47699, 48539, 49331, 49667, 49739, 50051, 50891, 51059, 51419, 51827, 51971, 52067, 54419, 54539, 55619, 56267, 56891, 57347, 57899, 58787, 58907, 59219, 59627, 60659, 60899, 61331, 62987, 63419, 63587, 64187, 64451, 65027, 65099, 65171, 65267, ...

Are there infinitely many such primes?
sweety439 is offline   Reply With Quote
Old 2020-01-19, 14:58   #7
sweety439
 
sweety439's Avatar
 
Nov 2016

22×13×37 Posts
Default

Quote:
Originally Posted by sweety439 View Post
For gaps between primes p which 2 is primitive root mod p:

A more generalization: gaps of primes p such that znorder(Mod(b,p)) = (p-1)/a, for fixed integers a>=1, b>=2 (for some (a,b) pairs such primes do not exist, e.g. (4,3) and (5,5)).
For the smallest prime p such that znorder(Mod(m,p)) = (p-1)/n, for fixed integers 2<=m<=32, 1<=n<=32 (0 if not exist):

Code:
m\n 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32,
2: 3, 7, 43, 113, 251, 31, 1163, 73, 397, 151, 331, 1753, 4421, 631, 3061, 257, 1429, 127, 6043, 3121, 29611, 1321, 18539, 601, 15451, 14327, 2971, 2857, 72269, 3391, 683, 2593,
3: 2, 11, 67, 13, 41, 61, 883, 313, 271, 431, 5743, 193, 3511, 1583, 2131, 433, 2551, 4177, 8513, 2521, 8779, 683, 10627, 1321, 29851, 1223, 3079, 9661, 49939, 661, 101681, 4129,
4: 0, 3, 0, 17, 0, 31, 0, 73, 0, 151, 0, 433, 0, 631, 0, 337, 0, 127, 0, 241, 0, 331, 0, 601, 0, 4421, 0, 673, 0, 3061, 0, 257,
5: 2, 11, 13, 101, 0, 199, 827, 569, 487, 31, 1453, 181, 7853, 71, 0, 401, 5407, 379, 15277, 761, 1303, 2069, 5107, 409, 0, 1171, 5077, 3109, 1973, 2521, 5023, 449,
6: 11, 19, 7, 5, 31, 139, 463, 97, 37, 101, 353, 241, 4889, 43, 421, 5233, 6563, 1747, 8171, 1901, 11551, 3719, 3037, 409, 28001, 26833, 26407, 11789, 5801, 3931, 48299, 15073,
7: 2, 3, 73, 29, 1031, 19, 43, 113, 883, 311, 353, 1453, 2861, 281, 181, 1873, 409, 1531, 191, 1621, 2311, 419, 14629, 5233, 12251, 7333, 32941, 4397, 11717, 811, 23251, 1409,
8: 3, 17, 13, 113, 251, 7, 1163, 89, 109, 431, 1013, 577, 4421, 953, 571, 257, 4523, 127, 15467, 3761, 3109, 7151, 18539, 73, 25301, 14327, 2971, 42953, 72269, 151, 683, 12641,
9: 0, 5, 0, 13, 0, 67, 0, 313, 0, 41, 0, 61, 0, 883, 0, 433, 0, 271, 0, 2161, 0, 683, 0, 193, 0, 1223, 0, 8317, 0, 2131, 0, 769,
10: 7, 3, 103, 53, 11, 79, 211, 41, 73, 281, 353, 37, 2393, 449, 3061, 1889, 137, 2467, 16189, 641, 3109, 4973, 11087, 1321, 101, 7151, 7669, 757, 38629, 1231, 49663, 12289,
11: 2, 7, 193, 5, 191, 19, 379, 449, 199, 1301, 2531, 1549, 2081, 547, 61, 1697, 2789, 523, 28843, 661, 1303, 1013, 18539, 2377, 4001, 1847, 31267, 6917, 10499, 1231, 39929, 6689,
12: 5, 23, 19, 37, 271, 13, 29, 193, 487, 11, 89, 373, 521, 421, 211, 5521, 7243, 829, 2129, 1741, 20707, 1453, 10903, 673, 17551, 4993, 12799, 5209, 233, 3181, 25793, 3169,
13: 2, 3, 7, 17, 331, 103, 2017, 673, 1657, 311, 463, 1213, 0, 1303, 271, 337, 1123, 1171, 19001, 61, 421, 7283, 4049, 2617, 1151, 157, 3889, 701, 8237, 601, 71983, 641,
14: 3, 5, 37, 113, 41, 67, 71, 401, 1459, 61, 463, 13, 3121, 659, 1381, 977, 41413, 1009, 1597, 461, 967, 8779, 23369, 12049, 9151, 547, 811, 8233, 132299, 5431, 148367, 2081,
15: 2, 11, 31, 53, 761, 7, 1163, 257, 3691, 311, 991, 1549, 443, 617, 2551, 2417, 1361, 1801, 2129, 3541, 3697, 1123, 12329, 5641, 4651, 2393, 4159, 113, 9629, 1201, 23003, 1249,
16: 0, 3, 0, 5, 0, 31, 0, 17, 0, 151, 0, 109, 0, 631, 0, 113, 0, 127, 0, 1181, 0, 331, 0, 433, 0, 13963, 0, 1709, 0, 3331, 0, 1217,
17: 2, 13, 73, 149, 181, 223, 29, 257, 541, 101, 2003, 229, 1093, 1471, 991, 433, 0, 883, 2851, 1361, 3361, 1409, 19183, 3673, 13901, 3719, 7723, 8093, 6091, 2371, 10789, 1889,
18: 5, 7, 13, 73, 131, 79, 1667, 41, 19, 311, 3917, 1201, 443, 113, 1381, 17, 1259, 199, 229, 2801, 1429, 881, 1427, 1153, 18701, 599, 12853, 6833, 20939, 2671, 19469, 3361,
19: 2, 3, 97, 101, 131, 307, 1303, 233, 271, 1291, 199, 277, 859, 197, 691, 1217, 12037, 487, 24967, 1901, 1009, 8999, 2393, 4561, 4951, 5227, 6373, 8513, 56957, 151, 14447, 2753,
20: 3, 11, 7, 29, 0, 151, 197, 521, 577, 71, 617, 61, 1873, 491, 0, 1489, 307, 19, 7753, 661, 127, 4049, 9293, 1129, 0, 859, 3673, 3221, 44777, 691, 8123, 929,
21: 2, 37, 13, 5, 11, 43, 953, 337, 433, 461, 199, 1129, 599, 211, 661, 881, 3877, 1747, 14897, 3301, 0, 1277, 52901, 1801, 14551, 30707, 2971, 14197, 34337, 1171, 41231, 1697,
22: 5, 3, 43, 13, 241, 7, 631, 521, 73, 461, 23, 613, 157, 127, 5791, 433, 10337, 2647, 37013, 401, 4201, 947, 17021, 97, 12101, 3407, 15013, 6329, 14153, 1381, 12959, 353,
23: 2, 7, 31, 29, 71, 103, 239, 233, 163, 11, 859, 1093, 53, 911, 271, 1153, 7039, 2719, 25423, 461, 211, 1013, 5843, 3889, 1901, 79, 57349, 1933, 13399, 2131, 17299, 4129,
24: 7, 5, 61, 29, 131, 67, 127, 457, 613, 311, 199, 2617, 79, 379, 991, 241, 4999, 307, 12541, 6581, 8527, 23, 11777, 1009, 1451, 4967, 22303, 2381, 349, 1321, 5023, 4801,
25: 0, 3, 0, 29, 0, 13, 0, 569, 0, 31, 0, 181, 0, 71, 0, 401, 0, 379, 0, 641, 0, 1453, 0, 409, 0, 1171, 0, 3109, 0, 2851, 0, 8609,
26: 3, 11, 151, 5, 31, 19, 547, 313, 1657, 1031, 859, 37, 6397, 3823, 181, 337, 4421, 3853, 4409, 7741, 757, 2311, 37307, 8161, 3701, 2393, 19441, 1597, 1567, 5101, 23561, 4001,
27: 2, 11, 7, 0, 41, 37, 1289, 0, 307, 431, 9857, 13, 7853, 1583, 1051, 0, 7481, 73, 8513, 0, 883, 683, 14813, 313, 38501, 1223, 271, 0, 59393, 661, 101681, 0,
28: 5, 3, 61, 53, 601, 199, 127, 449, 1423, 281, 4093, 1117, 3719, 29, 631, 113, 4999, 613, 23447, 541, 547, 6359, 6211, 6073, 14851, 4733, 4159, 6469, 33641, 4561, 1861, 6113,
29: 2, 5, 31, 13, 61, 7, 617, 1289, 541, 571, 727, 181, 2549, 673, 3121, 2609, 1259, 3061, 2927, 11981, 757, 67, 12743, 7321, 11701, 313, 16417, 12853, 0, 1831, 8123, 12577,
30: 11, 7, 73, 17, 991, 19, 1289, 257, 163, 71, 67, 277, 53, 1163, 31, 113, 1259, 613, 7069, 461, 337, 947, 9293, 409, 401, 1171, 3673, 29, 52259, 241, 14323, 10337,
31: 2, 3, 13, 5, 191, 271, 659, 977, 37, 541, 5237, 349, 4759, 911, 4111, 1217, 2143, 2683, 2129, 3221, 2689, 3499, 2531, 2857, 7901, 1613, 11827, 2437, 45821, 571, 40487, 577,
32: 3, 7, 43, 113, 11, 223, 1163, 73, 397, 41, 1013, 1753, 4733, 673, 691, 257, 1429, 127, 6043, 281, 33013, 6337, 18539, 1777, 251, 14327, 5347, 2857, 72269, 31, 683, 2593,
For more values (2<=m<=64, 1<=n<=64), see https://de.wikipedia.org/w/index.php...ldid=195976169

Last fiddled with by sweety439 on 2020-01-19 at 15:13
sweety439 is offline   Reply With Quote
Old 2020-01-19, 15:35   #8
sweety439
 
sweety439's Avatar
 
Nov 2016

192410 Posts
Default

Quote:
Originally Posted by sweety439 View Post
For the smallest prime p such that znorder(Mod(m,p)) = (p-1)/n, for fixed integers 2<=m<=32, 1<=n<=32 (0 if not exist):

Code:
m\n 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32,
2: 3, 7, 43, 113, 251, 31, 1163, 73, 397, 151, 331, 1753, 4421, 631, 3061, 257, 1429, 127, 6043, 3121, 29611, 1321, 18539, 601, 15451, 14327, 2971, 2857, 72269, 3391, 683, 2593,
3: 2, 11, 67, 13, 41, 61, 883, 313, 271, 431, 5743, 193, 3511, 1583, 2131, 433, 2551, 4177, 8513, 2521, 8779, 683, 10627, 1321, 29851, 1223, 3079, 9661, 49939, 661, 101681, 4129,
4: 0, 3, 0, 17, 0, 31, 0, 73, 0, 151, 0, 433, 0, 631, 0, 337, 0, 127, 0, 241, 0, 331, 0, 601, 0, 4421, 0, 673, 0, 3061, 0, 257,
5: 2, 11, 13, 101, 0, 199, 827, 569, 487, 31, 1453, 181, 7853, 71, 0, 401, 5407, 379, 15277, 761, 1303, 2069, 5107, 409, 0, 1171, 5077, 3109, 1973, 2521, 5023, 449,
6: 11, 19, 7, 5, 31, 139, 463, 97, 37, 101, 353, 241, 4889, 43, 421, 5233, 6563, 1747, 8171, 1901, 11551, 3719, 3037, 409, 28001, 26833, 26407, 11789, 5801, 3931, 48299, 15073,
7: 2, 3, 73, 29, 1031, 19, 43, 113, 883, 311, 353, 1453, 2861, 281, 181, 1873, 409, 1531, 191, 1621, 2311, 419, 14629, 5233, 12251, 7333, 32941, 4397, 11717, 811, 23251, 1409,
8: 3, 17, 13, 113, 251, 7, 1163, 89, 109, 431, 1013, 577, 4421, 953, 571, 257, 4523, 127, 15467, 3761, 3109, 7151, 18539, 73, 25301, 14327, 2971, 42953, 72269, 151, 683, 12641,
9: 0, 5, 0, 13, 0, 67, 0, 313, 0, 41, 0, 61, 0, 883, 0, 433, 0, 271, 0, 2161, 0, 683, 0, 193, 0, 1223, 0, 8317, 0, 2131, 0, 769,
10: 7, 3, 103, 53, 11, 79, 211, 41, 73, 281, 353, 37, 2393, 449, 3061, 1889, 137, 2467, 16189, 641, 3109, 4973, 11087, 1321, 101, 7151, 7669, 757, 38629, 1231, 49663, 12289,
11: 2, 7, 193, 5, 191, 19, 379, 449, 199, 1301, 2531, 1549, 2081, 547, 61, 1697, 2789, 523, 28843, 661, 1303, 1013, 18539, 2377, 4001, 1847, 31267, 6917, 10499, 1231, 39929, 6689,
12: 5, 23, 19, 37, 271, 13, 29, 193, 487, 11, 89, 373, 521, 421, 211, 5521, 7243, 829, 2129, 1741, 20707, 1453, 10903, 673, 17551, 4993, 12799, 5209, 233, 3181, 25793, 3169,
13: 2, 3, 7, 17, 331, 103, 2017, 673, 1657, 311, 463, 1213, 0, 1303, 271, 337, 1123, 1171, 19001, 61, 421, 7283, 4049, 2617, 1151, 157, 3889, 701, 8237, 601, 71983, 641,
14: 3, 5, 37, 113, 41, 67, 71, 401, 1459, 61, 463, 13, 3121, 659, 1381, 977, 41413, 1009, 1597, 461, 967, 8779, 23369, 12049, 9151, 547, 811, 8233, 132299, 5431, 148367, 2081,
15: 2, 11, 31, 53, 761, 7, 1163, 257, 3691, 311, 991, 1549, 443, 617, 2551, 2417, 1361, 1801, 2129, 3541, 3697, 1123, 12329, 5641, 4651, 2393, 4159, 113, 9629, 1201, 23003, 1249,
16: 0, 3, 0, 5, 0, 31, 0, 17, 0, 151, 0, 109, 0, 631, 0, 113, 0, 127, 0, 1181, 0, 331, 0, 433, 0, 13963, 0, 1709, 0, 3331, 0, 1217,
17: 2, 13, 73, 149, 181, 223, 29, 257, 541, 101, 2003, 229, 1093, 1471, 991, 433, 0, 883, 2851, 1361, 3361, 1409, 19183, 3673, 13901, 3719, 7723, 8093, 6091, 2371, 10789, 1889,
18: 5, 7, 13, 73, 131, 79, 1667, 41, 19, 311, 3917, 1201, 443, 113, 1381, 17, 1259, 199, 229, 2801, 1429, 881, 1427, 1153, 18701, 599, 12853, 6833, 20939, 2671, 19469, 3361,
19: 2, 3, 97, 101, 131, 307, 1303, 233, 271, 1291, 199, 277, 859, 197, 691, 1217, 12037, 487, 24967, 1901, 1009, 8999, 2393, 4561, 4951, 5227, 6373, 8513, 56957, 151, 14447, 2753,
20: 3, 11, 7, 29, 0, 151, 197, 521, 577, 71, 617, 61, 1873, 491, 0, 1489, 307, 19, 7753, 661, 127, 4049, 9293, 1129, 0, 859, 3673, 3221, 44777, 691, 8123, 929,
21: 2, 37, 13, 5, 11, 43, 953, 337, 433, 461, 199, 1129, 599, 211, 661, 881, 3877, 1747, 14897, 3301, 0, 1277, 52901, 1801, 14551, 30707, 2971, 14197, 34337, 1171, 41231, 1697,
22: 5, 3, 43, 13, 241, 7, 631, 521, 73, 461, 23, 613, 157, 127, 5791, 433, 10337, 2647, 37013, 401, 4201, 947, 17021, 97, 12101, 3407, 15013, 6329, 14153, 1381, 12959, 353,
23: 2, 7, 31, 29, 71, 103, 239, 233, 163, 11, 859, 1093, 53, 911, 271, 1153, 7039, 2719, 25423, 461, 211, 1013, 5843, 3889, 1901, 79, 57349, 1933, 13399, 2131, 17299, 4129,
24: 7, 5, 61, 29, 131, 67, 127, 457, 613, 311, 199, 2617, 79, 379, 991, 241, 4999, 307, 12541, 6581, 8527, 23, 11777, 1009, 1451, 4967, 22303, 2381, 349, 1321, 5023, 4801,
25: 0, 3, 0, 29, 0, 13, 0, 569, 0, 31, 0, 181, 0, 71, 0, 401, 0, 379, 0, 641, 0, 1453, 0, 409, 0, 1171, 0, 3109, 0, 2851, 0, 8609,
26: 3, 11, 151, 5, 31, 19, 547, 313, 1657, 1031, 859, 37, 6397, 3823, 181, 337, 4421, 3853, 4409, 7741, 757, 2311, 37307, 8161, 3701, 2393, 19441, 1597, 1567, 5101, 23561, 4001,
27: 2, 11, 7, 0, 41, 37, 1289, 0, 307, 431, 9857, 13, 7853, 1583, 1051, 0, 7481, 73, 8513, 0, 883, 683, 14813, 313, 38501, 1223, 271, 0, 59393, 661, 101681, 0,
28: 5, 3, 61, 53, 601, 199, 127, 449, 1423, 281, 4093, 1117, 3719, 29, 631, 113, 4999, 613, 23447, 541, 547, 6359, 6211, 6073, 14851, 4733, 4159, 6469, 33641, 4561, 1861, 6113,
29: 2, 5, 31, 13, 61, 7, 617, 1289, 541, 571, 727, 181, 2549, 673, 3121, 2609, 1259, 3061, 2927, 11981, 757, 67, 12743, 7321, 11701, 313, 16417, 12853, 0, 1831, 8123, 12577,
30: 11, 7, 73, 17, 991, 19, 1289, 257, 163, 71, 67, 277, 53, 1163, 31, 113, 1259, 613, 7069, 461, 337, 947, 9293, 409, 401, 1171, 3673, 29, 52259, 241, 14323, 10337,
31: 2, 3, 13, 5, 191, 271, 659, 977, 37, 541, 5237, 349, 4759, 911, 4111, 1217, 2143, 2683, 2129, 3221, 2689, 3499, 2531, 2857, 7901, 1613, 11827, 2437, 45821, 571, 40487, 577,
32: 3, 7, 43, 113, 11, 223, 1163, 73, 397, 41, 1013, 1753, 4733, 673, 691, 257, 1429, 127, 6043, 281, 33013, 6337, 18539, 1777, 251, 14327, 5347, 2857, 72269, 31, 683, 2593,
Also see https://de.wikipedia.org/w/index.php...ldid=195978132 for 2<=m<=128, 1<=n<=128 (0 if not exist). (I searched up to p=2^24, and I assume that there are no p>2^24 which is the smallest prime such that znorder(Mod(m,p)) = (p-1)/n for some m,n <= 128, in the list, the largest such prime is 2334251 (for m=126, n=125), and 2334251 is just between 2^21 and 2^22)

Last fiddled with by sweety439 on 2020-01-19 at 16:11
sweety439 is offline   Reply With Quote
Old 2020-01-19, 16:12   #9
sweety439
 
sweety439's Avatar
 
Nov 2016

22·13·37 Posts
Default

Quote:
Originally Posted by sweety439 View Post
For the smallest prime p such that znorder(Mod(m,p)) = (p-1)/n, for fixed integers 2<=m<=32, 1<=n<=32 (0 if not exist):

Code:
m\n 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32,
2: 3, 7, 43, 113, 251, 31, 1163, 73, 397, 151, 331, 1753, 4421, 631, 3061, 257, 1429, 127, 6043, 3121, 29611, 1321, 18539, 601, 15451, 14327, 2971, 2857, 72269, 3391, 683, 2593,
3: 2, 11, 67, 13, 41, 61, 883, 313, 271, 431, 5743, 193, 3511, 1583, 2131, 433, 2551, 4177, 8513, 2521, 8779, 683, 10627, 1321, 29851, 1223, 3079, 9661, 49939, 661, 101681, 4129,
4: 0, 3, 0, 17, 0, 31, 0, 73, 0, 151, 0, 433, 0, 631, 0, 337, 0, 127, 0, 241, 0, 331, 0, 601, 0, 4421, 0, 673, 0, 3061, 0, 257,
5: 2, 11, 13, 101, 0, 199, 827, 569, 487, 31, 1453, 181, 7853, 71, 0, 401, 5407, 379, 15277, 761, 1303, 2069, 5107, 409, 0, 1171, 5077, 3109, 1973, 2521, 5023, 449,
6: 11, 19, 7, 5, 31, 139, 463, 97, 37, 101, 353, 241, 4889, 43, 421, 5233, 6563, 1747, 8171, 1901, 11551, 3719, 3037, 409, 28001, 26833, 26407, 11789, 5801, 3931, 48299, 15073,
7: 2, 3, 73, 29, 1031, 19, 43, 113, 883, 311, 353, 1453, 2861, 281, 181, 1873, 409, 1531, 191, 1621, 2311, 419, 14629, 5233, 12251, 7333, 32941, 4397, 11717, 811, 23251, 1409,
8: 3, 17, 13, 113, 251, 7, 1163, 89, 109, 431, 1013, 577, 4421, 953, 571, 257, 4523, 127, 15467, 3761, 3109, 7151, 18539, 73, 25301, 14327, 2971, 42953, 72269, 151, 683, 12641,
9: 0, 5, 0, 13, 0, 67, 0, 313, 0, 41, 0, 61, 0, 883, 0, 433, 0, 271, 0, 2161, 0, 683, 0, 193, 0, 1223, 0, 8317, 0, 2131, 0, 769,
10: 7, 3, 103, 53, 11, 79, 211, 41, 73, 281, 353, 37, 2393, 449, 3061, 1889, 137, 2467, 16189, 641, 3109, 4973, 11087, 1321, 101, 7151, 7669, 757, 38629, 1231, 49663, 12289,
11: 2, 7, 193, 5, 191, 19, 379, 449, 199, 1301, 2531, 1549, 2081, 547, 61, 1697, 2789, 523, 28843, 661, 1303, 1013, 18539, 2377, 4001, 1847, 31267, 6917, 10499, 1231, 39929, 6689,
12: 5, 23, 19, 37, 271, 13, 29, 193, 487, 11, 89, 373, 521, 421, 211, 5521, 7243, 829, 2129, 1741, 20707, 1453, 10903, 673, 17551, 4993, 12799, 5209, 233, 3181, 25793, 3169,
13: 2, 3, 7, 17, 331, 103, 2017, 673, 1657, 311, 463, 1213, 0, 1303, 271, 337, 1123, 1171, 19001, 61, 421, 7283, 4049, 2617, 1151, 157, 3889, 701, 8237, 601, 71983, 641,
14: 3, 5, 37, 113, 41, 67, 71, 401, 1459, 61, 463, 13, 3121, 659, 1381, 977, 41413, 1009, 1597, 461, 967, 8779, 23369, 12049, 9151, 547, 811, 8233, 132299, 5431, 148367, 2081,
15: 2, 11, 31, 53, 761, 7, 1163, 257, 3691, 311, 991, 1549, 443, 617, 2551, 2417, 1361, 1801, 2129, 3541, 3697, 1123, 12329, 5641, 4651, 2393, 4159, 113, 9629, 1201, 23003, 1249,
16: 0, 3, 0, 5, 0, 31, 0, 17, 0, 151, 0, 109, 0, 631, 0, 113, 0, 127, 0, 1181, 0, 331, 0, 433, 0, 13963, 0, 1709, 0, 3331, 0, 1217,
17: 2, 13, 73, 149, 181, 223, 29, 257, 541, 101, 2003, 229, 1093, 1471, 991, 433, 0, 883, 2851, 1361, 3361, 1409, 19183, 3673, 13901, 3719, 7723, 8093, 6091, 2371, 10789, 1889,
18: 5, 7, 13, 73, 131, 79, 1667, 41, 19, 311, 3917, 1201, 443, 113, 1381, 17, 1259, 199, 229, 2801, 1429, 881, 1427, 1153, 18701, 599, 12853, 6833, 20939, 2671, 19469, 3361,
19: 2, 3, 97, 101, 131, 307, 1303, 233, 271, 1291, 199, 277, 859, 197, 691, 1217, 12037, 487, 24967, 1901, 1009, 8999, 2393, 4561, 4951, 5227, 6373, 8513, 56957, 151, 14447, 2753,
20: 3, 11, 7, 29, 0, 151, 197, 521, 577, 71, 617, 61, 1873, 491, 0, 1489, 307, 19, 7753, 661, 127, 4049, 9293, 1129, 0, 859, 3673, 3221, 44777, 691, 8123, 929,
21: 2, 37, 13, 5, 11, 43, 953, 337, 433, 461, 199, 1129, 599, 211, 661, 881, 3877, 1747, 14897, 3301, 0, 1277, 52901, 1801, 14551, 30707, 2971, 14197, 34337, 1171, 41231, 1697,
22: 5, 3, 43, 13, 241, 7, 631, 521, 73, 461, 23, 613, 157, 127, 5791, 433, 10337, 2647, 37013, 401, 4201, 947, 17021, 97, 12101, 3407, 15013, 6329, 14153, 1381, 12959, 353,
23: 2, 7, 31, 29, 71, 103, 239, 233, 163, 11, 859, 1093, 53, 911, 271, 1153, 7039, 2719, 25423, 461, 211, 1013, 5843, 3889, 1901, 79, 57349, 1933, 13399, 2131, 17299, 4129,
24: 7, 5, 61, 29, 131, 67, 127, 457, 613, 311, 199, 2617, 79, 379, 991, 241, 4999, 307, 12541, 6581, 8527, 23, 11777, 1009, 1451, 4967, 22303, 2381, 349, 1321, 5023, 4801,
25: 0, 3, 0, 29, 0, 13, 0, 569, 0, 31, 0, 181, 0, 71, 0, 401, 0, 379, 0, 641, 0, 1453, 0, 409, 0, 1171, 0, 3109, 0, 2851, 0, 8609,
26: 3, 11, 151, 5, 31, 19, 547, 313, 1657, 1031, 859, 37, 6397, 3823, 181, 337, 4421, 3853, 4409, 7741, 757, 2311, 37307, 8161, 3701, 2393, 19441, 1597, 1567, 5101, 23561, 4001,
27: 2, 11, 7, 0, 41, 37, 1289, 0, 307, 431, 9857, 13, 7853, 1583, 1051, 0, 7481, 73, 8513, 0, 883, 683, 14813, 313, 38501, 1223, 271, 0, 59393, 661, 101681, 0,
28: 5, 3, 61, 53, 601, 199, 127, 449, 1423, 281, 4093, 1117, 3719, 29, 631, 113, 4999, 613, 23447, 541, 547, 6359, 6211, 6073, 14851, 4733, 4159, 6469, 33641, 4561, 1861, 6113,
29: 2, 5, 31, 13, 61, 7, 617, 1289, 541, 571, 727, 181, 2549, 673, 3121, 2609, 1259, 3061, 2927, 11981, 757, 67, 12743, 7321, 11701, 313, 16417, 12853, 0, 1831, 8123, 12577,
30: 11, 7, 73, 17, 991, 19, 1289, 257, 163, 71, 67, 277, 53, 1163, 31, 113, 1259, 613, 7069, 461, 337, 947, 9293, 409, 401, 1171, 3673, 29, 52259, 241, 14323, 10337,
31: 2, 3, 13, 5, 191, 271, 659, 977, 37, 541, 5237, 349, 4759, 911, 4111, 1217, 2143, 2683, 2129, 3221, 2689, 3499, 2531, 2857, 7901, 1613, 11827, 2437, 45821, 571, 40487, 577,
32: 3, 7, 43, 113, 11, 223, 1163, 73, 397, 41, 1013, 1753, 4733, 673, 691, 257, 1429, 127, 6043, 281, 33013, 6337, 18539, 1777, 251, 14327, 5347, 2857, 72269, 31, 683, 2593,
For more values (2<=m<=64, 1<=n<=64), see https://de.wikipedia.org/w/index.php...ldid=195976169
The p for (m,n) = (9,1) and (25,1) are 2, not 0
sweety439 is offline   Reply With Quote
Old 2020-01-19, 22:20   #10
sweety439
 
sweety439's Avatar
 
Nov 2016

192410 Posts
Default

Quote:
Originally Posted by sweety439 View Post
For the smallest prime p such that znorder(Mod(m,p)) = (p-1)/n, for fixed integers 2<=m<=32, 1<=n<=32 (0 if not exist):

Code:
m\n 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32,
2: 3, 7, 43, 113, 251, 31, 1163, 73, 397, 151, 331, 1753, 4421, 631, 3061, 257, 1429, 127, 6043, 3121, 29611, 1321, 18539, 601, 15451, 14327, 2971, 2857, 72269, 3391, 683, 2593,
3: 2, 11, 67, 13, 41, 61, 883, 313, 271, 431, 5743, 193, 3511, 1583, 2131, 433, 2551, 4177, 8513, 2521, 8779, 683, 10627, 1321, 29851, 1223, 3079, 9661, 49939, 661, 101681, 4129,
4: 0, 3, 0, 17, 0, 31, 0, 73, 0, 151, 0, 433, 0, 631, 0, 337, 0, 127, 0, 241, 0, 331, 0, 601, 0, 4421, 0, 673, 0, 3061, 0, 257,
5: 2, 11, 13, 101, 0, 199, 827, 569, 487, 31, 1453, 181, 7853, 71, 0, 401, 5407, 379, 15277, 761, 1303, 2069, 5107, 409, 0, 1171, 5077, 3109, 1973, 2521, 5023, 449,
6: 11, 19, 7, 5, 31, 139, 463, 97, 37, 101, 353, 241, 4889, 43, 421, 5233, 6563, 1747, 8171, 1901, 11551, 3719, 3037, 409, 28001, 26833, 26407, 11789, 5801, 3931, 48299, 15073,
7: 2, 3, 73, 29, 1031, 19, 43, 113, 883, 311, 353, 1453, 2861, 281, 181, 1873, 409, 1531, 191, 1621, 2311, 419, 14629, 5233, 12251, 7333, 32941, 4397, 11717, 811, 23251, 1409,
8: 3, 17, 13, 113, 251, 7, 1163, 89, 109, 431, 1013, 577, 4421, 953, 571, 257, 4523, 127, 15467, 3761, 3109, 7151, 18539, 73, 25301, 14327, 2971, 42953, 72269, 151, 683, 12641,
9: 0, 5, 0, 13, 0, 67, 0, 313, 0, 41, 0, 61, 0, 883, 0, 433, 0, 271, 0, 2161, 0, 683, 0, 193, 0, 1223, 0, 8317, 0, 2131, 0, 769,
10: 7, 3, 103, 53, 11, 79, 211, 41, 73, 281, 353, 37, 2393, 449, 3061, 1889, 137, 2467, 16189, 641, 3109, 4973, 11087, 1321, 101, 7151, 7669, 757, 38629, 1231, 49663, 12289,
11: 2, 7, 193, 5, 191, 19, 379, 449, 199, 1301, 2531, 1549, 2081, 547, 61, 1697, 2789, 523, 28843, 661, 1303, 1013, 18539, 2377, 4001, 1847, 31267, 6917, 10499, 1231, 39929, 6689,
12: 5, 23, 19, 37, 271, 13, 29, 193, 487, 11, 89, 373, 521, 421, 211, 5521, 7243, 829, 2129, 1741, 20707, 1453, 10903, 673, 17551, 4993, 12799, 5209, 233, 3181, 25793, 3169,
13: 2, 3, 7, 17, 331, 103, 2017, 673, 1657, 311, 463, 1213, 0, 1303, 271, 337, 1123, 1171, 19001, 61, 421, 7283, 4049, 2617, 1151, 157, 3889, 701, 8237, 601, 71983, 641,
14: 3, 5, 37, 113, 41, 67, 71, 401, 1459, 61, 463, 13, 3121, 659, 1381, 977, 41413, 1009, 1597, 461, 967, 8779, 23369, 12049, 9151, 547, 811, 8233, 132299, 5431, 148367, 2081,
15: 2, 11, 31, 53, 761, 7, 1163, 257, 3691, 311, 991, 1549, 443, 617, 2551, 2417, 1361, 1801, 2129, 3541, 3697, 1123, 12329, 5641, 4651, 2393, 4159, 113, 9629, 1201, 23003, 1249,
16: 0, 3, 0, 5, 0, 31, 0, 17, 0, 151, 0, 109, 0, 631, 0, 113, 0, 127, 0, 1181, 0, 331, 0, 433, 0, 13963, 0, 1709, 0, 3331, 0, 1217,
17: 2, 13, 73, 149, 181, 223, 29, 257, 541, 101, 2003, 229, 1093, 1471, 991, 433, 0, 883, 2851, 1361, 3361, 1409, 19183, 3673, 13901, 3719, 7723, 8093, 6091, 2371, 10789, 1889,
18: 5, 7, 13, 73, 131, 79, 1667, 41, 19, 311, 3917, 1201, 443, 113, 1381, 17, 1259, 199, 229, 2801, 1429, 881, 1427, 1153, 18701, 599, 12853, 6833, 20939, 2671, 19469, 3361,
19: 2, 3, 97, 101, 131, 307, 1303, 233, 271, 1291, 199, 277, 859, 197, 691, 1217, 12037, 487, 24967, 1901, 1009, 8999, 2393, 4561, 4951, 5227, 6373, 8513, 56957, 151, 14447, 2753,
20: 3, 11, 7, 29, 0, 151, 197, 521, 577, 71, 617, 61, 1873, 491, 0, 1489, 307, 19, 7753, 661, 127, 4049, 9293, 1129, 0, 859, 3673, 3221, 44777, 691, 8123, 929,
21: 2, 37, 13, 5, 11, 43, 953, 337, 433, 461, 199, 1129, 599, 211, 661, 881, 3877, 1747, 14897, 3301, 0, 1277, 52901, 1801, 14551, 30707, 2971, 14197, 34337, 1171, 41231, 1697,
22: 5, 3, 43, 13, 241, 7, 631, 521, 73, 461, 23, 613, 157, 127, 5791, 433, 10337, 2647, 37013, 401, 4201, 947, 17021, 97, 12101, 3407, 15013, 6329, 14153, 1381, 12959, 353,
23: 2, 7, 31, 29, 71, 103, 239, 233, 163, 11, 859, 1093, 53, 911, 271, 1153, 7039, 2719, 25423, 461, 211, 1013, 5843, 3889, 1901, 79, 57349, 1933, 13399, 2131, 17299, 4129,
24: 7, 5, 61, 29, 131, 67, 127, 457, 613, 311, 199, 2617, 79, 379, 991, 241, 4999, 307, 12541, 6581, 8527, 23, 11777, 1009, 1451, 4967, 22303, 2381, 349, 1321, 5023, 4801,
25: 0, 3, 0, 29, 0, 13, 0, 569, 0, 31, 0, 181, 0, 71, 0, 401, 0, 379, 0, 641, 0, 1453, 0, 409, 0, 1171, 0, 3109, 0, 2851, 0, 8609,
26: 3, 11, 151, 5, 31, 19, 547, 313, 1657, 1031, 859, 37, 6397, 3823, 181, 337, 4421, 3853, 4409, 7741, 757, 2311, 37307, 8161, 3701, 2393, 19441, 1597, 1567, 5101, 23561, 4001,
27: 2, 11, 7, 0, 41, 37, 1289, 0, 307, 431, 9857, 13, 7853, 1583, 1051, 0, 7481, 73, 8513, 0, 883, 683, 14813, 313, 38501, 1223, 271, 0, 59393, 661, 101681, 0,
28: 5, 3, 61, 53, 601, 199, 127, 449, 1423, 281, 4093, 1117, 3719, 29, 631, 113, 4999, 613, 23447, 541, 547, 6359, 6211, 6073, 14851, 4733, 4159, 6469, 33641, 4561, 1861, 6113,
29: 2, 5, 31, 13, 61, 7, 617, 1289, 541, 571, 727, 181, 2549, 673, 3121, 2609, 1259, 3061, 2927, 11981, 757, 67, 12743, 7321, 11701, 313, 16417, 12853, 0, 1831, 8123, 12577,
30: 11, 7, 73, 17, 991, 19, 1289, 257, 163, 71, 67, 277, 53, 1163, 31, 113, 1259, 613, 7069, 461, 337, 947, 9293, 409, 401, 1171, 3673, 29, 52259, 241, 14323, 10337,
31: 2, 3, 13, 5, 191, 271, 659, 977, 37, 541, 5237, 349, 4759, 911, 4111, 1217, 2143, 2683, 2129, 3221, 2689, 3499, 2531, 2857, 7901, 1613, 11827, 2437, 45821, 571, 40487, 577,
32: 3, 7, 43, 113, 11, 223, 1163, 73, 397, 41, 1013, 1753, 4733, 673, 691, 257, 1429, 127, 6043, 281, 33013, 6337, 18539, 1777, 251, 14327, 5347, 2857, 72269, 31, 683, 2593,
For more values (2<=m<=64, 1<=n<=64), see https://de.wikipedia.org/w/index.php...ldid=195976169
If n == 2 mod 4, then such prime exists for every m>=2

If n is divisible by 12, then such prime exists for every m>=2

Such prime does not exist if and only if one of these three conditions holds: (note that any pair of two of these three conditions cannot both hold)

* m is square, n is odd, n > 1

* Let m' be the squarefree part of m, m' == 1 mod 4, m' > 1, n is odd, and n is multiple of m'

* m is of the form 27*k^6, n == 4 or 8 mod 12

Code:
m    n such that such prime does not exist
4    m == 1 mod 2
5    m == 5 mod 10
9    m == 1 mod 2 (except m = 1)
13   m == 13 mod 26
16   m == 1 mod 2
17   m == 17 mod 34
20   m == 5 mod 10
21   m == 21 mod 42
25   m == 1 mod 2 (except m = 1)
27   m == 4, 8 mod 12
29   m == 29 mod 58
33   m == 33 mod 66
36   m == 1 mod 2
37   m == 37 mod 74
41   m == 41 mod 82
45   m == 5 mod 10
49   m == 1 mod 2 (except m = 1)
52   m == 13 mod 26
53   m == 53 mod 106
57   m == 57 mod 114
61   m == 61 mod 122
64   m == 1 mod 2
65   m == 65 mod 130
68   m == 17 mod 34
69   m == 69 mod 138
73   m == 73 mod 146
77   m == 77 mod 154
80   m == 5 mod 10
81   m == 1 mod 2 (except m = 1)
84   m == 21 mod 42
85   m == 85 mod 170
89   m == 89 mod 178
93   m == 93 mod 186
97   m == 97 mod 194
100  m == 1 mod 2
101  m == 101 mod 202
105  m == 105 mod 210
109  m == 109 mod 218
113  m == 113 mod 226
116  m == 29 mod 58
117  m == 13 mod 26
121  m == 1 mod 2 (except m = 1)
125  m == 5 mod 10

Last fiddled with by sweety439 on 2020-01-19 at 22:35
sweety439 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Gaps of Primes? PawnProver44 Miscellaneous Math 10 2016-04-10 19:32
Primitive roots for a set of primes mart_r Math 0 2013-07-20 12:23
Primitive Roots Numbers Math 16 2005-09-21 23:41
Is 3 always a primitive root for mersenne primes? juergen Math 12 2005-03-09 08:18
Is 3 always a primitive root for mersenne primes? juergen Programming 9 2005-03-08 03:51

All times are UTC. The time now is 21:01.

Thu May 28 21:01:19 UTC 2020 up 64 days, 18:34, 0 users, load averages: 1.21, 1.42, 1.44

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.