# 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". Commented Jul 29, 2018 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$? Commented Jul 30, 2018 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). Commented Jul 30, 2018 at 16:21

## 1 Answer

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!