# Question about the proportions of primes p for which $ord_p(2)$ satisfies certain congruences

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?

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)$.

• Waouh. This is a clear explanation, if not a proof, because of the need of Riemann hypothesis. – René Gy Jun 1 '14 at 8:30
• 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. – René Gy Jun 1 '14 at 8:39
• 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$ ... – René Gy Jun 1 '14 at 11:59
• I guess I can agree with "slightly bizarre". :) – Greg Martin Jun 1 '14 at 19:20
• 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. – Greg Martin Jun 1 '14 at 19:21