4
$\begingroup$

let $p$ be a prime. I have observed numerically that the proportion of $p$ satisfying $ord_p(2)\equiv4[8]$ seems to be $1/3$. Why is it so? Is there a simple proof?

Moreover the proportion $c$ of prime $p$ satisfying $ord_p(2)\equiv2[4]$ seems to be the same as the proportion of primes $p$ for which $ord_p(2)\equiv1[2]$ or those $ord_p(2)$ which are odd. Again, why is it so?

$c\approx0.29..$ Who is that number?

$\endgroup$
5
$\begingroup$

Recall that each residue class $1,3,5,7\pmod8$ contains $\frac14$ of the primes, asymptotically, by the prime number theorem for arithmetic progressions.

If $p\equiv3\pmod8$, then $p-1\equiv2\pmod4$, and $2$ is a quadratic nonresidue modulo $p$, which means that $ord_p(2)\equiv2\pmod4$ as well.

If $p\equiv7\pmod8$, then again $p-1\equiv2\pmod4$, but $2$ is now a quadratic residue modulo $p$, which means that $ord_p(2)\equiv1\pmod2$.

If $p\equiv5\pmod8$, then $p-1\equiv4\pmod8$, and $2$ is a quadratic nonresidue modulo $p$, which means that $ord_p(2)\equiv4\pmod8$ as well.

Finally, suppose that $p\equiv1\pmod8$, and let $k$ be the the exponent of $2$ in the factorization of $p-1$, so that $k\ge3$. Note that among these primes, $k=3$ for $\frac12$ of them, $k=4$ for $\frac14$ of them, $k=5$ for $\frac18$ of them, etc., again by the prime number theorem for arithmetic progressions.

Let $j$ be the the exponent of $2$ in the factorization of $ord_p(2)$. Since $2$ is a quadratic residue modulo $p$, we know that $j\le k-1$. We have $j=k-1$ if and only if $2$ is not a fourth power modulo $p$; $j=k-1$ if and only if $2$ is a fourth power but not an eighth power modulo $p$; $j=k-1$ if and only if $2$ is an eighth power but not a sixteenth power modulo $p$; and so on until $j=0$ if and only if $2$ is a $2^k$th power modulo $p$.

We can show (possibly requiring the assumption of a suitable generalized Riemann hypothesis) that among the primes $p\equiv1\pmod8$, $2$ is not a fourth power for $\frac12$ of them; $2$ is a fourth power but not an eighth power for $\frac14$ of them; $2$ is an eighth power but not a sixteenth power for $\frac18$ of them; and so on. (This is what we'd expect on the heuristic that $2$ is randomly distributed among the quadratic residues modulo $p$.)

Therefore the proportion of primes $p$ such that $ord_p(2)\equiv4\pmod8$ equals $$ 0+0+\frac14+\frac14\bigg( \frac12\cdot\frac12+\frac14\cdot\frac14+\frac18\cdot\frac18+\cdots \bigg) = \frac13. $$ Similarly, the proportion of primes $p$ such that $ord_p(2)\equiv2\pmod4$ equals $$ \frac14+0+0+\frac14\bigg( \frac12\cdot\frac14+\frac14\cdot\frac18+\frac18\cdot\frac1{16}+\cdots \bigg) = \frac7{24} = 0.291\bar6. $$ A similar calculation gives $\frac7{24}$ for the proportion of primes $p$ such that $ord_p(2)$ is odd. Finally, the proportion of primes $p$ such that $ord_p(2)\equiv2^k\pmod{2^{k+1}}$ is $1/(3\cdot2^k)$.

$\endgroup$
  • $\begingroup$ Waouh. This is a clear explanation, if not a proof, because of the need of Riemann hypothesis. $\endgroup$ – René Gy Jun 1 '14 at 8:30
  • $\begingroup$ I was wrongly pursuing the numerical investigation, trying to see if $c$ would eventually approach closer to $1-\sqrt{2}/2$ but the convergence is slow and somewhat erratic. $\endgroup$ – René Gy Jun 1 '14 at 8:39
  • $\begingroup$ in your last statement, $k\ge3$, so that at the end, after summing these proportions over all $k\ge0$, one recovers 100% of the primes. Isn't it slightly bizarre that the biggest proportion is for $k=2$? and not $k=1$ ... $\endgroup$ – René Gy Jun 1 '14 at 11:59
  • $\begingroup$ I guess I can agree with "slightly bizarre". :) $\endgroup$ – Greg Martin Jun 1 '14 at 19:20
  • $\begingroup$ By the way, to figure out whether we really need the GRH or whether we can prove these statements unconditionally, I would suggest looking at the work of Adam Felix. $\endgroup$ – Greg Martin Jun 1 '14 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.