# Can a primitive root-permutation of $A=\{1, 2, \ldots, p-1 \}$ be a cycle of length $p-1$ only for finitely many $p$?

Let $p$ be an odd prime, $g$ a primitive root of $p$ and $A=\{1, 2, \ldots, p-1 \}$.

Obviously, $\sigma_g(p)=\begin{pmatrix} 1 & 2 & \ldots & {p-1} \\ g^1\pmod{p} & g^2\pmod{p} & \ldots & g^{p-1}\pmod{p} \end{pmatrix}$ is a permutation of $A$.

I observed that "almost always" $\sigma$ is a product of cycles whose length is strictly less than $p-1$.
If $p=3$ and $g=2$, then $\sigma_2(3)=\begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix}=(1\quad2)$ is a cycle of length $3-1=2$.

If $p=5$ and $g=3$, then $\sigma_3(5)=\begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 4 & 2 & 1 \end{pmatrix}=(1\quad 3\quad 2\quad 4)$ is a cycle of length $5-1=4$.
But these two cases seem to be just exceptions.
For other (small) values of $p$ and every primitive root $g$ of $p$, there are no cycles of length $p-1$.

I can prove that $g=2$ and $g=\frac{p+1}{2}$ cannot produce such a big cycle, but I do not have any idea how to attack the problem for other values of $g$.
I conjecture that for every $g$ there is not such a big cycle (for sufficiently large $p$)

My question is:

Do only finitely many primes $p$ exist, such that for some primitive root $g$ the permutation $\sigma_g(p)=\begin{pmatrix} 1 & 2 & \ldots & {p-1} \\ g^1\pmod{p} & g^2\pmod{p} & \ldots & g^{p-1}\pmod{p} \end{pmatrix}$ is a cycle?

• Apparently, there are a lot of counterexamples. Smallest ones are $p = 23, g = 20$; $p = 41, g = 6$; $p = 59, g = 39$; $p = 61, g = 10$; $p = 107, g = 94$. They don't stop appearing as $p$ grows either (and there are $p$-s, for which more than one $g$ is suitable). So it seems that the answer is more probably "No" than "Yes". – Kaban-5 Jul 29 '18 at 22:04
• @Kaban-5 what are the first few $p$ for which there is more than one $g$ leading to a $(p-1)$-cycle, and what are all such $g$ for those $p$? – KConrad Jul 30 '18 at 11:42
• Two possible $g$'s: $p = 587, g = 150, 375$; $p = 751, g = 240, 263$; $p = 809, g = 265, 750$; $p = 811, g = 113, 165$. Three: $p = 1889, g = 479, 859, 1248$; $p = 2267, g = 61, 976, 2010$; $p = 2699, g = 427, 639, 1256$; $p = 3491, g = 1472, 1626, 1833$. Four: $p = 5417, g = 1319, 1566, 3486, 5290$; $p = 7691, g = 558, 1434, 6244, 6760$. Five and more does not happen for $p \leqslant 10^4$. I believe that this should happen eventually anyway because heuristics suggest that, at least assuming that the number of Sophie Germain primes is infinite (probably unnecessary). – Kaban-5 Jul 30 '18 at 16:21

As pointed out in the comments, primitive roots with a single cycle appear to be rather common. The standard heuristic argument suggests that there are infinitely many such $p$, and a bit more.
The share of $N$-cycles among all permutations on $N$ symbols is $1/N$. By the Borel-Cantelli lemma, given an infinite sequence $\{\sigma_i\}$ of independent uniformly distributed random permutations on $N_i$ symbols, if $\sum 1/N_i$ diverges then with probability one infinitely many $\sigma_i$ constitute a single cycle. Since the series of reciprocal primes diverges, we may expect that given a random sequence $\{g_i\}$ of primitive roots mod $p_i$ over all primes, with probability one there are infinitely many $\sigma_i=\sigma_{g_i}(p_i)$ that constitute a single cycle. Of course, since uniform distribution and independence are only heuristic, this is not a proof!