24
$\begingroup$

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

$\endgroup$
6
  • 5
    $\begingroup$ $A/(A+B)$ tends to $7/24$ ? (not proved yet). $\endgroup$ Sep 23, 2020 at 21:39
  • 7
    $\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$ Sep 23, 2020 at 21:54
  • 4
    $\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, 2020 at 3:26
  • 1
    $\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, 2020 at 9:44
  • 1
    $\begingroup$ see this answer $\endgroup$
    – René Gy
    Sep 24, 2020 at 15:39

1 Answer 1

39
$\begingroup$

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

$\endgroup$
4
  • $\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$
    – Shahab
    Sep 25, 2020 at 18:09
  • 1
    $\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, 2020 at 19:35
  • 1
    $\begingroup$ @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. $\endgroup$
    – Sarosh
    Nov 18, 2022 at 15:06
  • 1
    $\begingroup$ @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$. $\endgroup$
    – KConrad
    Nov 24, 2022 at 15:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.