Orders in residue classes
Written by Claude Opus 5.5 (Anthropic) on 24 October 2026. The question was posed by Claude while writing this course and solved by GPT-6 Astra (OpenAI) in ChatGPT's Pro mode; the solution was refereed by Claude Opus 5.5 in a separate session, and this lesson was written from it, refereed and revised by Claude Opus 5.5 in two further sessions, and checked and finished by Claude Opus 5.5 in a fourth. Public domain (CC0).
Fix \(a\in\mathbb Z\) with \(A=|a|>1\), an integer \(d\ge1\) and \(r\in\mathbb Z\). This lesson studies the primes \(p\nmid a\) with \(\operatorname{ord}_p(a)\equiv r\pmod d\). Theorem 4.1 of Divisibility of the multiplicative order shows, unconditionally, that each such class contains infinitely many primes: at least a constant multiple of \(\log x\) of them up to \(x\). The questions here concern lower bounds of size \(x/L^2\) in \((x,2x)\).
- Section 1 decomposes the count by the index.
- Section 2 reduces a lower bound of size \(x/L^2\) to a supply of controlled-predecessor primes with a finite Frobenius condition, and shows that the condition is nonempty in every class.
- Section 3 gives the classes reached by the predecessor sieve.
- Section 4 shows that the class \(2\bmod15\) receives only \(o(x/L^2)\) of the sieve's primes.
The analytic input enters through Complete splitting at composite levels.
Prerequisites.
- Artin's conjecture and the index of a prime, Section 1, (4.1) and Proposition 5.1.
- Complete splitting at composite levels, Proposition 1.2, Lemma 3.1 and Theorems 4.1 and 5.1.
- Divisibility of the multiplicative order, Theorem 4.1.
- Primes with controlled predecessors, Theorem 6.1.
- Hilbert's ramification theory in Galois extensions, Theorem 6.2, Proposition 6.3 and Corollary 6.5.
Throughout, \(L=\log x\), \(y=\exp(L^{0.1})\), \(z=\exp(L^{0.3})\), \(\delta_0=10^{-6}\), and \(A=b^h\) as in Section 1 of Complete splitting at composite levels. For \(p\nmid a\), \(i_p(a)=(p-1)/\operatorname{ord}_p(a)\) is the index, and \(K_n=\mathbb Q(\mu_n,a^{1/n})\). Put \[ \begin{aligned} &N_a(r,d;x)=\#\{p\le x:\ p\nmid a,\\ &\qquad\operatorname{ord}_p(a)\equiv r\ (\mathrm{mod}\ d)\}. \end{aligned} \]
1. Decomposition by the index
Lemma 1.1. Let \(p\nmid a\) and \(t\ge1\). The conditions "\(i_p(a)=t\) and \(\operatorname{ord}_p(a)\equiv r\pmod d\)" and "\(i_p(a)=t\) and \(p\equiv1+tr\pmod{dt}\)" are equivalent. Hence \(N_a(r,d;x)\) is the sum over \(t<x\) of the number of primes \(p\le x\), \(p\nmid a\), with \(i_p(a)=t\) and \(p\equiv1+tr\pmod{dt}\), and the sets for different \(t\) are disjoint.
Proof. We have \(p-1=t\operatorname{ord}_p(a)\). Multiplication by \(t\) carries \(\operatorname{ord}_p(a)\equiv r\pmod d\) to \(p-1\equiv tr\pmod{dt}\), and division by \(t\) reverses this. The index is unique, and \(t\le p-1<x\). \(\square\)
2. A Frobenius condition for a prescribed class
Let \(t\ge1\), let \(C\) be even with \(t\mid C\), and assume \((1+tr,dt)=1\).
Let \(\alpha_C\) be a root of \(T^C-a\) and put \(\Omega=K_C(\zeta_{dt})\). This is the splitting field of \((X^{dt}-1)(X^C-a)\), so it is Galois over \(\mathbb Q\). For \(s\mid C\), \(K_s\) is the Galois subfield generated by \(\zeta_C^{C/s}\) and \(\alpha_C^{C/s}\).
Let \(\Sigma\) be the set of \(\sigma\in\operatorname{Gal}(\Omega/\mathbb Q)\) such that:
- \(\sigma|_{K_t}=1\);
- \(\sigma|_{K_{t\ell}}\ne1\) for every prime \(\ell\mid C\) with \(t\ell\mid C\);
- \(\sigma(\zeta_{dt})=\zeta_{dt}^{1+tr}\).
Lemma 2.1. The set \(\Sigma\) is stable under conjugation. Every prime \(p\nmid aCdt\) is unramified in \(\Omega\); if \(\sigma\) is its Frobenius at a prime \(\mathfrak P\) of \(\Omega\), then \(\sigma(\zeta_{dt})=\zeta_{dt}^p\), and for \(s\mid C\) the restriction \(\sigma|_{K_s}\) is the Frobenius of \(\mathfrak P\cap K_s\).
Let \(p_1\nmid 2ad\) be a prime with \(\operatorname{ord}_{p_1}(a)\equiv r\pmod d\). Put \(t=i_{p_1}(a)\) and \(C=\prod_{\ell\mid2dt}\ell^{v_\ell(p_1-1)}\). Then:
- \(C\) is even and \(t\mid C\);
- \((1+tr,dt)=1\);
- the Frobenius class of \(p_1\) in \(\Omega\) lies in \(\Sigma\).
Proof. Conjugation. Restriction to a Galois subfield is a homomorphism, so \((\tau\sigma\tau^{-1})|_K\) is trivial exactly when \(\sigma|_K\) is. The group \(\operatorname{Gal}(\mathbb Q(\zeta_{dt})/\mathbb Q)\) is abelian, so conjugation does not change the action on \(\zeta_{dt}\).
Ramification and Frobenius. Let \(p\nmid aCdt\). The discriminants of \(X^{dt}-1\) and \(X^C-a\) are supported on the primes dividing \(dt\) and \(aC\), so at a prime \(\mathfrak P\mid p\) the roots of each factor have distinct reductions. Inertia acts trivially on residues (Theorem 6.2 of the ramification lesson) and permutes the roots of each factor. It therefore fixes every root, and the roots generate \(\Omega\). Let \(\sigma\) be the Frobenius of \(\mathfrak P\) (Proposition 6.3 there), so that \(\sigma(\beta)\equiv\beta^p\pmod{\mathfrak P}\) for every integer \(\beta\) of \(\Omega\). The elements \(\sigma(\zeta_{dt})\) and \(\zeta_{dt}^p\) lie in \(\mu_{dt}\) and are congruent modulo \(\mathfrak P\); reduction is injective on \(\mu_{dt}\), so they are equal. The congruence restricts to the integers of \(K_s\), which gives the last claim.
The witness. Since \(p_1\) is odd, \(v_2(p_1-1)\ge1\), so \(C\) is even. Since \(t\mid p_1-1\) and every prime factor of \(t\) divides \(2dt\), \(t\mid C\). From \(C\mid p_1-1\) and \(t\mid p_1-1\) we get \(p_1\nmid Ct\); hence \(p_1\nmid aCdt\).
Lemma 1.1 gives \(p_1\equiv1+tr\pmod{dt}\), and \((p_1,dt)=1\) then gives \((1+tr,dt)=1\).
Let \(\sigma\) be the Frobenius at a prime of \(\Omega\) above \(p_1\). By Lemma 3.1 of Complete splitting at composite levels, applied to the restrictions of \(\sigma\):
- \(t\mid i_{p_1}(a)\) gives \(\sigma|_{K_t}=1\);
- for \(\ell\mid C\), \(p_1\nmid at\ell\) holds, and \(t\ell\nmid i_{p_1}(a)\) gives \(\sigma|_{K_{t\ell}}\ne1\).
Finally \(\sigma(\zeta_{dt})=\zeta_{dt}^{p_1}=\zeta_{dt}^{1+tr}\). By stability, the whole class lies in \(\Sigma\). \(\square\)
Theorem 4.1 of Divisibility of the multiplicative order gives infinitely many primes in every class, hence a prime \(p_1\nmid2ad\) in every class. So \(\Sigma\ne\emptyset\) for some \((t,C)\) in every class \(r\bmod d\).
Theorem 2.2. Let \(t,C,\Sigma\) be as above and fix \(\kappa>0\). Suppose that, for large \(x\), at least \(\kappa x/L^2\) primes \(p\in(x,2x)\) satisfy both of the following:
- \(p-1=CRQ\), where \(Q>x^{0.9}\) is prime and every prime factor of \(R\) lies in \((y,z)\);
- the Frobenius class of \(p\) in \(\Omega\) lies in \(\Sigma\).
Then, for large \(x\), at least \(\frac\kappa2x/L^2\) primes \(p\in(x,2x)\) have \(p\nmid a\) and \(\operatorname{ord}_p(a)\equiv r\pmod d\).
Proof. Take \(x>|a|Cdt\) and \(y>C\). Then each such \(p\) satisfies \(p\nmid aCdt\), so it is unramified in \(\Omega\) by Lemma 2.1, and \(p\nmid at\ell\) for \(\ell\mid C\). All prime factors of \(RQ\) exceed \(C\), so \(v_\ell(p-1)=v_\ell(C)\) for \(\ell\mid C\).
Let \(\sigma\) be the Frobenius of \(p\) at a prime of \(\Omega\). Triviality on \(K_t\) gives \(t\mid i_p(a)\) by Lemma 3.1 of Complete splitting at composite levels. Suppose \(\ell\mid C\) and \(v_\ell(i_p(a))>v_\ell(t)\). Then \(t\ell\mid i_p(a)\mid p-1\), so \(v_\ell(t\ell)\le v_\ell(C)\); with \(t\mid C\) this gives \(t\ell\mid C\). The same lemma then makes \(\sigma|_{K_{t\ell}}\) trivial, which contradicts \(\Sigma\). Hence \(v_\ell(i_p(a))=v_\ell(t)\) for every \(\ell\mid C\).
Theorem 5.1 there, with \(m=t\), gives at least \(\frac\kappa2x/L^2\) of these primes with \(i_p(a)=t\). By Lemma 2.1, \(\sigma(\zeta_{dt})=\zeta_{dt}^p\), and \(\sigma\in\Sigma\) gives \(\zeta_{dt}^p=\zeta_{dt}^{1+tr}\), so \(p\equiv1+tr\pmod{dt}\). Lemma 1.1 then gives \(\operatorname{ord}_p(a)\equiv r\pmod d\). \(\square\)
3. Classes reached by the predecessor sieve
Theorem 6.1 of Primes with controlled predecessors does not involve \(a\). Let \(M\) be a positive multiple of \(8\), \(c\in\{2,4\}\), and \(u\) an integer satisfying (4.1) of Artin's conjecture and the index of a prime. Then there is \(\kappa>0\) such that, for large \(x\), at least \(\kappa x/L^2\) primes \(p\in(x,2x)\) have \(p\equiv u\pmod M\) and \(p-1=cRQ\), with \(Q>x^{0.9}\) prime and every prime factor of \(R\) in \((y,z)\).
Proposition 3.1. Let \(M\), \(c\) and \(u\) be as above.
- If \(\bigl(\frac ap\bigr)=-1\) for every prime \(p\equiv u\pmod M\), then for large \(x\) at least \(\frac\kappa2x/L^2\) primes \(p\in(x,2x)\) have \(\operatorname{ord}_p(a)\equiv u-1\pmod d\), for every \(d\mid M\).
- If \(c=2\) and \(\bigl(\frac ap\bigr)=1\) for every prime \(p\equiv u\pmod M\) with \(p\nmid a\), then for large \(x\) the same count holds with \(\operatorname{ord}_p(a)\equiv(u-1)/2\pmod d\), for every \(d\) with \(2d\mid M\).
Proof. Take \(x>A\), so that the primes of Theorem 6.1 do not divide \(a\), and apply Theorem 5.1 of Complete splitting at composite levels to them with \(C=c\), whose only prime factor is \(2\).
- By Euler's criterion, \(i_p(a)\) is odd. This is the valuation condition for \(m=1\), so \(\frac\kappa2x/L^2\) primes have \(i_p(a)=1\). For them \(\operatorname{ord}_p(a)=p-1\equiv u-1\pmod d\).
- Here \(2\mid i_p(a)\). For \(y>2\), \(R\) and \(Q\) are odd, so \(v_2(p-1)=1=v_2(i_p(a))\). Take \(m=2\). Then \(\operatorname{ord}_p(a)=(p-1)/2\), and \(p\equiv u\pmod{2d}\) gives \((p-1)/2\equiv(u-1)/2\pmod d\). \(\square\)
Example 3.2. Take \(a=2\).
- The triple \((8,2,3)\) satisfies (4.1), and \(\bigl(\frac2p\bigr)=-1\) for \(p\equiv3\pmod8\). Part 1 of Proposition 3.1 gives \(\operatorname{ord}_p(2)\equiv2\pmod8\).
- The triple \((8,2,7)\) satisfies (4.1), and \(\bigl(\frac2p\bigr)=1\) for \(p\equiv7\pmod8\). Part 2 with \(d=4\) gives \(\operatorname{ord}_p(2)\equiv3\pmod4\).
4. A class the sieve misses
Let \(\mathcal P_S(x)\) be the set of primes \(p\in(x,2x)\) with \(p-1=cRQ\), where \(c\in\{2,4\}\), \(Q>x^{0.9}\) is prime and every prime factor of \(R\) lies in \((y,z)\).
Proposition 4.1. For all large \(x\), \[ \begin{aligned} &\#\{p\in\mathcal P_S(x):\operatorname{ord}_p(a)\equiv2\ (15)\}\\ &\le C_*\Bigl(\frac{2x}{yL}+(4+\log A)zx^{1-\delta_0}\Bigr)\\ &\quad+\frac{4(\log A+1)x^{0.2}}{L}=o\Bigl(\frac x{L^2}\Bigr), \end{aligned} \] with \(C_*\) the constant of Theorem 4.1 of Complete splitting at composite levels.
Proof. Take \(x>A\), \(y>\max(h,5)\) and \(z<x\), and put \(t=i_p(a)\).
Some prime \(q\in(y,z)\) divides \(t\). Then \(p\) splits completely in \(K_q\) (Lemma 3.1 there), and \(d_q=q(q-1)\) (Proposition 1.2 there). Summing the bound of Theorem 4.1 there over \(q>y\), with \(\sum_{j>y}1/(j(j-1))\le2/y\), gives the first term.
\(Q\mid t\). Then \(\operatorname{ord}_p(a)<J=2x^{0.1}\), so \(p\) divides \(B=\prod_{j\le J}|a^j-1|\neq0\). Using \(|a^j-1|\le2A^j\), \[ \begin{aligned} \log B&\le J^2\log A+J\log2\\ &\le4x^{0.2}(\log A+1). \end{aligned} \] Each prime \(p>x\) dividing \(B\) uses at least \(L\) of this logarithm, which gives the second term.
Otherwise. Every prime factor of \(t\) is \(2\), and \(v_2(t)\le v_2(c)\), so \(t\in\{1,2,4\}\). Then \(p=1+t\operatorname{ord}_p(a)\equiv3,5,9\pmod{15}\), which is impossible for a prime \(p>5\).
The three terms are \(o(x/L^2)\), because \(2Le^{-L^{0.1}}\), \(L^2e^{L^{0.3}-\delta_0L}\) and \(Lx^{-0.8}\) all tend to \(0\). \(\square\)
The class \(2\bmod15\) is infinite by Theorem 4.1 of Divisibility of the multiplicative order. The argument of the third case shows that Theorem 2.2 can reach this class only with \(C\nmid4\): if \(C\mid4\), then \(t\mid C\) forces \(t\in\{1,2,4\}\), and then \((1+2t,15t)\ne1\), so the coprimality required in Section 2 fails. These statements concern what the sieve's stated output implies, not the truth of the lower bound.
5. Exercises
5.1. Show that \(p=43\) satisfies \(p\equiv3\pmod8\) but \(\operatorname{ord}_{43}(2)\not\equiv2\pmod8\). Which step in the proof of Part 1 of Proposition 3.1 excludes such primes?
5.2. Show that the third case of Proposition 4.1 gives no contradiction for the class \(1\bmod15\).
5.3. In Lemma 2.1, take \(a=2\), \(d=3\), \(r=1\) and \(p_1=11\). Compute \(t\) and \(C\).
6. Solutions
5.1. We have \(2^7=128=3\cdot43-1\), so \(2^7\equiv-1\) and \(2^{14}\equiv1\pmod{43}\). Since \(2\), \(2^2\) and \(2^7\) are not \(\equiv1\pmod{43}\), \(\operatorname{ord}_{43}(2)=14\equiv6\pmod8\), and \(i_{43}(2)=3\). The index is odd, as Euler's criterion requires, but it is not \(1\). In the proof, Theorem 5.1 of Complete splitting at composite levels with \(m=1\) keeps only the primes with \(i_p(a)=1\): the primes whose index has an odd prime factor are among the \(o(x/L^2)\) primes deleted there.
5.2. With \(t=1\), the condition \(\operatorname{ord}_p(a)\equiv1\pmod{15}\) gives \(p\equiv2\pmod{15}\), a class that contains primes.
5.3. Since \(2^5\equiv-1\pmod{11}\), \(\operatorname{ord}_{11}(2)=10\equiv1\pmod3\), so \(p_1\) lies in the class, and \(p_1\nmid2ad=12\). Then \(t=1\), \(2dt=6\), and \(C=2^{v_2(10)}3^{v_3(10)}=2\).
Sources
- [OpenAI-029] OpenAI, Primitive roots for every admissible integer base, OpenAI Math Release preprint, 4 October 2026, Proposition 2.1. https://github.com/openai/math/tree/main/preprints/Primitive-roots-for-every-admissible-integer-base-October-4-2026
- The main argument follows a solution produced with ChatGPT (OpenAI) in October 2026 and is completed here.