Cryptography Reference
In-Depth Information
(
,
)>
many? It is obvious that if gcd
1 then a common prime factor of
a
and
n
divides every term of the residue class, which can only contain at most one prime.
But if this trivial case is excluded, there is a classical theorem of Dirichlet showing
that the number of primes in the residue class is infinite (see, e.g., [77, Theorem
3.3.1]):
a
n
Theorem 6.3
(Dirichlet)
If a
,
n are integers such that n
>
0
and
gcd
(
a
,
n
)
=
1
,
then the arithmetic progression
{
a
,
a
+
n
,
a
+
2
n
,...
}
contains infinitely many primes.
Since the distribution of primes in large intervals is so regular, one can expect
not only that there are infinitely many primes in each of these arithmetic progres-
sions but also that the primes are uniformly distributed among them. Let us denote
by
π(
x
;
n
,
a
)
the number of primes
≤
x
that are congruent to
a
modulo
n
(where
gcd
(
a
,
n
)
=
1). The question is then to determine, given
x
and
n
, how alike are
the numbers
π(
x
;
n
,
a
)
for all the
a
<
n
such that gcd
(
a
,
n
)
=
1. In the following
10
7
.
exercise we check this for a couple of values of
n
when
x
=
Exercise 6.3
1.
(ii) Use the above procedure to compute the number of primes less than 10
7
that
end in 1, 3, 7, 9 (in the decimal numeration system).
(iii) Compute the number of primes
(i) Write a Maple procedure to compute
π(
x
;
n
,
a
)
when gcd
(
a
,
n
)
=
10
7
congruent to 1
<
,
2
,...,
10
(
mod11
)
.
10
7
[
,
]
interval, the primes
have an astoundingly uniform distribution across the residue classes. For example,
the number of primes ending in 1, 3, 7 and 9 are, respectively, 166104, 166230,
166211, and 166032. This is strongly reminiscent of the PNT and, indeed, there is
a version of the PNT for arithmetic progressions that was conjectured by Dirichlet
and Legendre and proved by de la Vallée Poussin:
The answer to the preceding exercise shows that, in the
2
Theorem 6.4
(PNT for arithmetic progressions)
For each n
,
a such that n
>
1
x
and
Li
(
x
)
φ(
and
gcd
(
a
,
n
)
=
1,
π(
x
;
n
,
a
)
is asymptotic to both
,
where
φ(
n
)
φ(
n
)
ln
x
n
)
denotes Euler's
φ
-
function
.
,
this theorem merely says that, asymptotically, the primes are uniformly distributed
among all the nontrivial residue classes modulo
n
. Not only that, but it is conjectured
that the error term of this approximation is small (of the same order as in the PNT),
which constitutes the
Extended Riemann Hypothesis
: if gcd
Observe that, since the number of
a
<
n
such that gcd
(
a
,
n
)
=
1 is precisely
φ(
n
)
(
a
,
n
)
=
1 then
Li
(
x
)
x
2
+
ε
).
π(
;
,
)
=
+
(
x
n
a
O
φ(
n
)
Remark 6.2
The PNT for arithmetic progressions has the following probabilistic
interpretation. If we draw a random integer
≤
x
from the congruence class
a
(
mod
n
)
,
where gcd
(
a
,
n
)
=
1, then this integer will be prime with probability asymptotic to
