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

  • 4
    $\begingroup$ $A/(A+B)$ tends to $7/24$ ? (not proved yet). $\endgroup$ – Henri Cohen Sep 23 '20 at 21:39
  • 4
    $\begingroup$ 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. $\endgroup$ – Joe Silverman Sep 23 '20 at 21:54
  • 3
    $\begingroup$ @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. $\endgroup$ – KConrad Sep 24 '20 at 3:26
  • $\begingroup$ 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. $\endgroup$ – YCor Sep 24 '20 at 9:44
  • $\begingroup$ see this answer $\endgroup$ – René Gy Sep 24 '20 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}$.

  • $\begingroup$ 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. $\endgroup$ – Mohsen Sep 25 '20 at 18:09
  • $\begingroup$ 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. $\endgroup$ – KConrad Sep 25 '20 at 19:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.