on the least primitive root of a prime

372 Views Asked by At

There is an article in this link. I am trying to understand it but some parts seem unclear to me. For example in part 3 I don't know how the following was derived: $$ \left ( 2^{m}-1 \right )p^{\frac{1}{2}}\left [ \frac{x}{2} \right ]\geq \left [ \frac{x}{2} \right ]^{2} $$ Can anyone kindly explain it?

$m$ is the number of distinct primes dividing $p−1$ .

1

There are 1 best solutions below

5
On BEST ANSWER

We have

$$\left\lfloor \frac x 2 \right \rfloor ^2 \leq \sum_{\substack{d | p-1 \\ d>1}} \frac{|\mu(d)|}{\phi(d)} \sum_{o(\chi)=d} p^{1/2} \left\lfloor \frac x 2 \right \rfloor.$$

The inner sum is over Dirichlet characters of order $d$ and modulus $p$. There are $\phi(d)$ of those, so we have

$$\left\lfloor \frac x 2 \right \rfloor ^2 \leq \sum_{\substack{d | p-1 \\ d>1}} |\mu(d)| p^{1/2} \left\lfloor \frac x 2 \right \rfloor.$$

Note that the Mobius function $\mu(d)$ is supported on square-free numbers. There are precisely $2^m$ square-free divisors $d$ of $p-1$, but we exclude $d=1$, so we have

$$\left\lfloor \frac x 2 \right \rfloor ^2 \leq (2^m-1) p^{1/2} \left\lfloor \frac x 2 \right \rfloor.$$