Parity of the multiplicative order of 2 modulo p

Question

Let $\operatorname{ord}_p(2)$ be the order of 2 in the multiplicative group modulo $p$. Let $A$ be the subset of primes $p$ where $\operatorname{ord}_p(2)$ is odd, and let $B$ be the subset of primes $p$ where $\operatorname{ord}_p(2)$ is even. Then how large is $A$ compared to $B$?

Answer 1

This problem was asked by Sierpiński in 1958 and answered by Hasse in the 1960s.

For each nonzero rational number $a$ (take $a \in \mathbf Z$ if you wish) and each prime $\ell$, let $S_{a,\ell}$ be the set of primes $p$ not dividing the numerator or denominator of $a$ such that $a \bmod p$ has multiplicative order divisible by $\ell$. When $a = \pm 1$, $S_{a,\ell}$ is empty except that $S_{-1,2}$ is all odd primes. From now on, suppose $a \not= \pm 1$.

In Math. Ann. 162 (1965/66), 74–76 (see Über die Dichte der Primzahlen $p$, für die eine vorgegebene ganzrationale Zahl $a \ne 0$ von durch eine vorgegebene Primzahl $l\ne 2$ teilbarer bzw. unteilbarer Ordnung mod.$p$ ist, and on MathSciNet see MR0186653) Hasse treated the case $\ell \ne 2$. Let $e$ be the largest nonnegative integer such that $a$ in $\mathbf Q$ is an $\ell^e$-th power. (For example, if $a$ is squarefree then $e = 0$ for every $\ell$ not dividing $a$.) The density of $S_{a,\ell}$ is $\ell/(\ell^e(\ell^2-1))$. This is $\ell/(\ell^2-1)$ when $e = 0$ and $1/(\ell^2-1)$ when $e = 1$.

In Math. Ann. 166 (1966), 19–23 (see Über die Dichte der Primzahlen $p$, für die eine vorgegebene ganzrationale Zahl $a\ne 0$ von gerader bzw. ungerader Ordnung mod.$p$ ist, and on MathSciNet see MR0205975) Hasse treated the case $\ell = 2$. The general answer in this case is more complicated, as issues like this often are when there are $\ell$-th roots of unity in the ground field, like $\pm 1$ in $\mathbf Q$ when $\ell = 2$. The density of $S_{a,2}$ for "typical" $a$ (such as integers $a \geq 3$ that are odd and squarefree, or more generally that are not a square or twice a square) is $2/3$, which is what we'd expect from Hasse's formula for $S_{a,\ell}$ when $\ell > 2$: $2/3 = 2/(2^2-1)$. But $S_{2,2}$ has density $17/24$ rather than $2/3$, so the set of primes $p$ such that $2 \bmod p$ has even order has density $17/24$ and the set of primes $p$ such that $2 \bmod p$ has odd order has density $1 - 17/24 = 7/24$.

To illustrate $S_{7,2}$ having density $2/3$, let's look at primes up to $10^6$. There are $78497$ primes $p \leq 10^6$ other than $7$, for $52339$ of these $p$ the order of $7 \bmod p$ is even, and $52339/78497 \approx .666764$, which is close to $2/3$.

To illustrate $S_{2,2}$ having density $17/24$, there are $167$ odd primes up to $1000$, $1228$ odd primes up to $10000$, and $9591$ odd primes up to $100000$. There are $117$ odd primes $p \leq 1000$ such that $2 \bmod p$ has even order, $878$ odd primes $p \leq 10000$ such that $2 \bmod p$ has even order, and $6794$ odd primes $p \leq 100000$ such that $2 \bmod p$ has even order. We have $17/24 \approx .70833$, while the proportion of odd primes up $1000$, $10000$, and $100000$ for which $2 \bmod p$ has even order is $117/167 \approx .700059$, $878/1228 \approx .71498$, and $6794/9591 \approx .70837$.

The math.stackexchange page About the parity of $\operatorname{ord}_p(7)$ treats $S_{7,2}$ in some detail and at the end mentions the case of $S_{2,2}$.