Skip to main content
2 of 3
(Some) typos fixed
Seva
  • 23k
  • 2
  • 59
  • 141

Why $\gcd \{ {\rm ord}_p(q)\colon q\mid p-1 \}$ likes to be large?

For a prime $p$, let $F_p$ denote the greatest common divisor of the orders modulo $p$ of all prime divisors of $p-1$: $$ F_p = \gcd \{ {\rm ord}_p(q)\colon q\mid p-1 \}; $$ thus, for instance, $F_3=2$, $F_5=4$, $F_7=3$, and $F_p$ is a divisor of $p-1$ for all $p$.

There exist primes $p$ with $F_p=1$, the smallest of them being $31$, $307$, and $601$. The strange thing is, there are rather few such primes; say, out of the 78,497 odd primes up to $10^6$, there are only 86 primes $p$ with $F_p=1$. Is there any explanation to this phenomenon?

Generally, $F_p$ tends to be large. The following histogram presents the "density function" of the quantity $\log F_p/\log p$, for all primes $p<10^6$:

$\hskip 1in$ Density Distribution http://math.haifa.ac.il/%7Eseva/MathOverflow/F-Histo.jpg

As the histogram shows, there are almost no primes $p$ with $F_p<p^{1/4}$, and for the vast majority of primes we actually have $F_p>\sqrt p$. This can also be read from the "cumulative distribution function":

$\hskip 1in$ Cumulative Distribution http://math.haifa.ac.il/%7Eseva/MathOverflow/F-Plot.jpg

Both plots behave rather enigmatically, but my major question is:

$\hskip 1in$ Why $F_p$ is "normally" that large? Why $F_p=1$ holds that rarely?

In case it matters, I am actually interested in the situation where $p\equiv 1\pmod 4$ and $p-1$ is $\sqrt p$-smooth.

Seva
  • 23k
  • 2
  • 59
  • 141