# Parity of the multiplicative order of 2 modulo p

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

• $A/(A+B)$ tends to $7/24$ ? (not proved yet). – Henri Cohen Sep 23 at 21:39
• Seems like an interesting question, and clearly generalizable quite a lot. However, if you're going to ask many questions on this site, it would be a good idea to learn a little bit of TeX formatting. I've fixed the formatting of your question, so if you click on "edit", you'll be able to see what I did to make it more readable. I also changed the title of your question to make it even clearer what you're asking. – Joe Silverman Sep 23 at 21:54
• @HenriCohen how did you determine $A/(A+B)$ to be $7/24$ while also writing "not proved yet"? The proportion of $p \leq 100000$ for which $2 \bmod p$ has odd order is $2797/9591$, which as a continued fraction is $[0,3,2,3,44,9]$, and the truncated continued fraction $[0,3,2,3]$ is $7/24$. I'd be interested to know if you did that or something else. – KConrad Sep 24 at 3:26
• Note: the set $A$ is at OEIS: oeis.org/A014663, while its complement $B$ is oeis.org/A091317. Among the 46 primes below 200, $A$ consists of the 14 primes 7, 23, 31, 47, 71, 73, 79, 89, 103, 127, 151, 167, 191, 199. – YCor Sep 24 at 9:44
• see this answer – René Gy Sep 24 at 15:39

This problem was asked by Sierpinski 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 (the paper is at https://eudml.org/doc/161322 and on MathSciNet see MR0186653) Hasse treated the case $$\ell \not= 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 (the paper is at https://eudml.org/doc/161442 and on MathSciNet see MR0205975) Hasse treated the case $$\ell = 2$$. The general answer in this case is more complicated, as issues involving $$\ell$$-th roots of unity in the ground field (like $$\pm 1$$ in $$\mathbf Q$$ when $$\ell = 2$$) often are. The density of $$S_{a,2}$$ for "typical" $$a$$ is $$1/3$$, such as when $$a \geq 3$$ is squarefree. But $$S_{2,2}$$ has density 17/24, so the set of $$p$$ for which $$2 \bmod p$$ has even order has density $$17/24$$ and the set of $$p$$ for which $$2 \bmod p$$ has odd order has density $$1 - 17/24 = 7/24$$.

For example, 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. 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$$, while $$17/24 \approx .70833$$.

The math.stackexchange page here treats $$S_{7,2}$$ in some detail and at the end mentions the case of $$S_{2,2}$$.

• Thanks @KConrad for the expression. I was thinking about a combinatorial property of cyclic groups of prime order(called acyclic matching property) and I proved the above mentioned sequence of primes does not hold it. See Proposition 2.3 of core.ac.uk/download/pdf/33123051.pdf Anyway I will like to mention this result in my ongoing research work as a remark, and hence I ask your permission for the same, of course with acknowledgment. – Mohsen Sep 25 at 18:09
• Since the result is due to Hasse, cite his paper when you want to indicate who first showed that the density exists and what its value is. – KConrad Sep 25 at 19:35