# 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). Sep 23, 2020 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. Sep 23, 2020 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. Sep 24, 2020 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, 2020 at 9:44
• see this answer Sep 24, 2020 at 15:39

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

• 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. Sep 25, 2020 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. Sep 25, 2020 at 19:35
• @KConrad The answer in the math.stackexchange page you linked that treats the case for a=7 and l=2, math.stackexchange.com/questions/3018887/…, says that the proportion of primes p such that the multiplicative order of a, a squarefree and greater or equal to 3, is odd is 1/3. However your answer says that the proportion of primes p such that the multiplicative order of a is even is 1/3. Both of these cannot be true so I was wondering if you could please clarify this. Seeing the other post and as S_2,2 is 17/24 I'd be inclined to think S_a,2 was 2/3. Nov 18 at 15:06
• @Sarosh I had a typographical error. I have now edited my answer and included a numerical example with $a=7$ and $\ell = 2$ to illustrate the density of $S_{7,2}$ being $2/3$. Nov 24 at 15:55