0
$\begingroup$

A primitive root $h$ of $n$ is a generator of the cyclic modulo multiplicative group $\mathbb{Z}^\times_n$.

Suppose, $\mathbb{P}_{\langle 2\rangle,N}=\{p_i <N\mid \langle 2\rangle=\mathbb{Z}^\times_{p_i}\}$ denotes the set of all primes $p_i<N$ that have a primtive root $2$. Let, $2^k\equiv x_i \mod{p_i}$, for some fixed even integer $k\gg\log{p_i}$ for all $p_i \in\mathbb{P}_{\langle 2\rangle,N}$.

My questions are,

  1. Is there any upper and lower bound on each $x_i$, even asymptotically? or do they have some special form?
  2. Is there any relation between any arbitrary pair $(x_i,x_j)$ for $i\ne j$?

In short, is it possible to predict $x_i$ even before $p_i$ is specified?

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ If I understand your question right, $x_i \geq 3$ should be the best possible lower bound (since $1$ and $2$ are impossible or obvious reasons). We can find examples where this bound is sharp by factoring $2^k-3$ - many prime factors should have $2$ as a primitive root. Some examples with $k/\log p$ small are $5,13,29, 61, 509$. $\endgroup$
    – Will Sawin
    Commented Apr 8 at 17:28
  • $\begingroup$ Thank you professor @WillSawin for this answer. If I understood correctly, in other words do you want say that $x_i=3$ for a non-negligible fraction of primes that have $2$ as one of their primitive roots? $\endgroup$
    – Somudro Gupto
    Commented Apr 8 at 18:47
  • $\begingroup$ Not necessarily a non-negligible fraction in the sense of positive density, but I would expect this does happen for infinitely many primes. $\endgroup$
    – Will Sawin
    Commented Apr 8 at 19:22
  • $\begingroup$ Yes, that is correct. Thank you again. It could be really helpful if this fraction could be expressed as a function of $N$. I think it needs a separate question. $\endgroup$
    – Somudro Gupto
    Commented Apr 8 at 19:56
  • 1
    $\begingroup$ For $k=(p_i-1)/2$ (and its odd multiples), we have $x_i=p_i-1$, which shows that no better upper bound is possible. $\endgroup$
    – Max Alekseyev
    Commented Apr 9 at 11:17

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .