It has been known for a long time that there are infinitely many prime numbers. A famous proof by Euclid goes like this:
Theorem 1 (Euclid). There are infinitely many prime numbers.
Proof. Suppose there are only finitely many prime numbers, and let us write them
. Consider the number
. By the unique factorization of integers, we know there is a prime
which divides
, but then
should be different from
(
), contradiction. ////
Remark 2. The key idea in the above proof is that if you have a finitely many prime numbers
, then
as defined above has another prime
as a factor. This idea of "constructing" a prime from a given set of primes can be generalized as follows.
Theorem 3. There are infinitely many primes which are congruent to 1 modulo 4, i.e. primes
of the form
for some positive integer
Proof. We use the fact that
is a prime congruent to 1 modulo 4 if and only if there is an integer
such that
Now write finitely many primes congruent to
as
. Then consider the number
. Any prime
dividing
--there is such a prime by the unique factorization property--is different from any of the primes
and 2. Since we obviously have
,
. Thus the theorem is true. ////
(Important) Remark 4. The idea in the both proofs is to find a polynomial
such that
has a prime divisor
and
belongs to a certain "class" of prime numbers, for example the set of primes numbers congruent to 1 modulo 4 .
Definition 5. 
, where
.
Lemma 6. Let
. Then
has infinitely many prime divisors as
runs through positive integers.
Proof. Omitted. ////
Lemma 7. If a prime
divides
for some positive integer
, then
. Here,
is the m-th cyclotomic polynomial
where
runs through the primitive m-th roots of unity.
Proof. Omitted. ////
The statements of Lemmas 6 and 7 are weaker than what was suggested in Remark 4, but they are still enough to deduce the following theorem, which is a particular case of the (weak) Dirichlet theorem.
Theorem. The cardinality of
is infinite.
Proof. Immediate from the lemmas. ////
0 comments:
Post a Comment