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$?



Parity of the multiplicative order of 2 modulo p
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](https://eudml.org/doc/161322), and on MathSciNet see [MR0186653](https://mathscinet.ams.org/mathscinet-getitem?mr=186653)) 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](https://eudml.org/doc/161442), and on MathSciNet see [MR0205975](https://mathscinet.ams.org/mathscinet-getitem?mr=205975)) 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)$](https://math.stackexchange.com/questions/3018887/about-the-parity-of-ord-p7) treats $S\_{7,2}$ in some detail and at the end mentions the case of $S\_{2,2}$.


