2
$\begingroup$

To mod $p=23,$ there are three sequences of two or more consecutive primitive roots. Namely $10,11$ and $14,15$ and $19,20,21.$ My question is whether there is a bound on the length of such sequences of consecutive primitive roots, or on the other hand is it the case that for any given $n$ there is a prime $p$ having a sequence of at least $n$ consecutive primitive roots.

Any reference about this is appreciated, as well as more examples of longer such sequences.

Edit: A search revealed a paper which purports that there are arbitrarily long sequences of consecutive primitive roots for sufficiently large primes $p.$ The techniques of the paper are over my head, though. So I'd appreciate a simpler approach.

https://www.ias.ac.in/article/fulltext/pmsc/123/02/0203-0211

$\endgroup$
4
  • 2
    $\begingroup$ I think this is genuinely a difficult and non-elementary problem. I don't know of an elementary proof that large primes $p$ must possess even two consecutive primitive roots, let alone many consecutive primitive roots. $\endgroup$ – Greg Martin Sep 10 '18 at 6:02
  • 1
    $\begingroup$ @GregMartin Yes, I agree it's likely essentially non-elementary. $\endgroup$ – coffeemath Sep 10 '18 at 6:04
  • $\begingroup$ @coffeemath Would you be content with a list of the smallest primes $p_k$ having at least $k$ consecutive primitive roots upto, lets say , $k=10$ ? $\endgroup$ – Peter Sep 16 '18 at 14:03
  • 1
    $\begingroup$ @Peter Given the paper I found (included in my question after a google search) I was looking for maybe a simpler proof. But such a list would be appreciated (including where these sequences start) $\endgroup$ – coffeemath Sep 16 '18 at 14:12
2
$\begingroup$

Upto $19$ , the smallest primes and the start-point of the smallest run (if more than one run exists) can be calculated by the following PARI/GP - program : First column : length , second column : smallest prime , third column : smallest starting point

? f(p)={v=select(m->znorder(Mod(m,p))==p-1,[1..p-1]);d=1;maxi=1;for(j=2,length(v
),if(v[j]-v[j-1]==1,d=d+1);if(v[j]-v[j-1]<>1,d=1);if(d>maxi,maxi=d;stelle=j));ma
xi}
%24 = (p)->v=select(m->znorder(Mod(m,p))==p-1,[1..p-1]);d=1;maxi=1;for(j=2,lengt
h(v),if(v[j]-v[j-1]==1,d=d+1);if(v[j]-v[j-1]<>1,d=1);if(d>maxi,maxi=d;stelle=j))
;maxi
? for(l=2,19,q=2;while(f(q)<>l,q=nextprime(q+1));print(l,"   ",q,"   ",v[stelle-
l+1]))
2   5   2
3   11   6
4   37   17
5   53   18
6   89   26
7   83   52
8   347   17
9   269   106
10   563   369
11   467   306
12   1187   1143
13   1907   1266
14   4007   2602
15   1559   1543
16   8363   5565
17   7727   4921
18   6803   4530
19   20327   16347
?

For length $21$, I found : 

21   10559   10537

and for length $22$ : 

22   35279   35256

I did not find a prime with exactly length $20$ or length more than $22$ yet.

$\endgroup$
1
  • 1
    $\begingroup$ Update : $45119$ has length $20$ starting at $43829$ and $38639$ has length $27$ starting at $38611$ $\endgroup$ – Peter Sep 16 '18 at 15:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.