19
$\begingroup$

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 (source)

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 (source)

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.

$\endgroup$
5
  • 10
    $\begingroup$ If $q|(p-1)$ and $a$ is coprime to $p$ then $q|\text{ord}_p(a)$ unless $a$ is a $q$-th power. Thus with probability $1-1/q$ we know that $q|\text{ord}_p(a)$. Use this idea with say the largest prime factor of $p-1$. Since $p-1$ has about $\log\log p$ prime factors, it is very likely that all of them are not $q$-th powers, and then $q$ will divide your gcd. Maybe this can be made rigorous with some work. $\endgroup$
    – Lucia
    Commented Oct 29, 2014 at 14:06
  • 1
    $\begingroup$ Thanks, Lucia, your remark is quite insightful (though it seems difficult to prove anything along these lines). $\endgroup$
    – Seva
    Commented Oct 29, 2014 at 16:30
  • 3
    $\begingroup$ Yes, it does seem difficult to prove anything. But your question only asked for explanations, not proofs! The heuristic above also suggests that in fact one should expect $F_p$ to be of size $p^{1-\epsilon}$ almost always. $\endgroup$
    – Lucia
    Commented Oct 29, 2014 at 16:44
  • 3
    $\begingroup$ If anyone is interested, here is a histogram of $F_p/p$: link It seems that a relatively large proportion of the prime have $F_p\sim p/2$. $\endgroup$
    – Liam Baker
    Commented Oct 30, 2014 at 7:30
  • 2
    $\begingroup$ @LiamBaker Since $F_p$ divides $p-1$ it would be more interesting to plot $(p-1)/F_p=\operatorname{lcm}(k\mid q \text{ prime divides } p-1, q=a^k)$ I think. Then many primes would give $2$ because presumably all prime factors of $p-1$ are at most squares (and not cubes etc). $\endgroup$ Commented Nov 24, 2014 at 21:26

0

You must log in to answer this question.

Browse other questions tagged .