Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Explicit bounds for primes in residue classes

Authors: Eric Bach and Jonathan Sorenson
Journal: Math. Comp. 65 (1996), 1717-1735
MSC (1991): Primary 11N13, 11M26; Secondary 11R44, 11Y35
MathSciNet review: 1355006
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let $E/K$ be an abelian extension of number fields, with $E \ne \Bbb Q$. Let $\Delta $ and $n$ denote the absolute discriminant and degree of $E$. Let $\sigma $ denote an element of the Galois group of $E/K$. We prove the following theorems, assuming the Extended Riemann Hypothesis:

There is a degree-$1$ prime ${\frak p}$ of $K$ such that $\left (\frac {\displaystyle \frak p}{E/K}\right ) =\sigma $, satisfying $N{\frak p}\le (1+o(1))(\log \Delta+2n)^2$.
There is a degree-$1$ prime $\frak p$ of $K$ such that $\left (\frac {\displaystyle \frak p}{E/K}\right )$ generates
the same group as $\sigma $, satisfying $N{\frak p}\le (1+o(1))(\log \Delta)^2$.
For $K=\Bbb Q$, there is a prime $p$ such that $\left (\frac {\displaystyle \frak p}{E/\Bbb Q }\right )=\sigma $, satisfying
$p\le (1+o(1))(\log \Delta)^2$.
In (1) and (2) we can in fact take $\frak p$ to be unramified in $K/\Bbb Q$. A special case of this result is the following.
If $\gcd (m,q)=1$, the least prime $p\equiv m\pmod q$ satisfies
$p\le (1+o(1))(\varphi (q)\log q)^2$.
It follows from our proof that (1)--(3) also hold for arbitrary Galois extensions, provided we replace $\sigma $ by its conjugacy class $\langle \sigma\rangle $. Our theorems lead to explicit versions of (1)--(4), including the following: the least prime $p \equiv m \pmod q$ is less than $ 2( q \log q )^2$.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (1991): 11N13, 11M26, 11R44, 11Y35

Retrieve articles in all journals with MSC (1991): 11N13, 11M26, 11R44, 11Y35

Additional Information

Eric Bach
Affiliation: Computer Sciences Department University of Wisconsin Madison, Wisconsin 53706

Jonathan Sorenson
Affiliation: Department of Mathematics and Computer Science Butler University Indianapolis, Indiana 46208

Received by editor(s): October 4, 1994
Received by editor(s) in revised form: September 5, 1995
Additional Notes: This research was supported in part by NSF grants CCR-9208639 and CCR-9204414, a grant from the Wisconsin Alumni Research Foundation, and a Butler University Fellowship
An extended abstract appeared in the Proceedings of Symposia in Applied Mathematics: Mathematics of Computation 1943–1993: A Half-Century of Computational Mathematics, Mathematics of Computation 50th Anniversary Symposium, August 9–13, 1993, Vancouver, British Columbia, as part of the Lehmer Minisymposium on computational number theory, Walter Gautschi, Editor, PSAPM volume 48, published by the American Mathematical Society, pp. 535–539
Article copyright: © Copyright 1996 American Mathematical Society