MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


Consider the multiplicative group $(\mathbb{Z}/p)^*$ for a given prime $p$. We know that the number of generators in this group is $\phi(p-1)$ --- the Euleur totient function. The question is, for $0 \leq a < a + \log^{c} p < b \leq p-1$ where $c$ is a constant (say $c=10$), how many generators of the group belongs to $[a,b]$? In other words, what is the density of generators in a given interval $[a,b]$ (compared to the density $\phi(p-1)/p-1$)? Is it easier if $b=p-1$?

For a given prime $p$, what is the densest interval in term of generators?

share|cite|improve this question
As far as I am aware, the shortest intervals known to include at least one generator have length $O((\log p)^2)$, assuming the Generalized Riemann Hypothesis. Unconditionally, you can’t even get anywhere near that. Thus, I doubt you can get any nontrivial answer. – Emil Jeřábek Mar 21 '12 at 19:48
No, sorry, this bound was for quadratic nonresidues. For generators, it is $O((\log p)^6)$, according to Wikipedia. – Emil Jeřábek Mar 21 '12 at 19:51
It is standard for $\mathbb{Z}_p$ to refer to $p$ adic number. You want the quotient by the prime ideal. – Marc Palm Mar 21 '12 at 21:04
It is standard for ${\bf Z}_p$ to refer to whatever the person using it says it refers to. The usage in this question was perfectly clear and not in any need of editing. – Gerry Myerson Mar 21 '12 at 21:52
A fairly standard character sum technique leads to the conclusion that the number of primitive roots mod $p$ in an interval of length $Q$ is $$ \frac{\phi(p-1)}{p-1)}\,\big(Q+2^{k+1}\theta\sqrt p\log p\big), $$ where $k$ is the number of distinct prime divisors of $p-1$ and $|\theta|<1$ (see Vinogradov's "Elements of Number Theory", Chapter VI, Problem 14-b-$\beta$). I hardly believe there are any substantial improvements known. – Seva Mar 22 '12 at 7:43

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.