there are an infinite number of primes
Theorem 1.
There are an infinite number of primes congruent
to .
Proof.
Choose any prime ; we find a prime of that form that exceeds .
Clearly , and thus must have at least one prime factor that is also . But is not divisible by any prime less than or equal to , so must be divisible by some prime congruent to that exceeds .∎
Theorem 2.
There are an infinite number of primes congruent to .
Proof.
Given , we find a prime with . Let be the smallest (odd) prime factor of ; note that . Now
and therefore
By Fermat’s little theorem, , so we have
The left-hand side cannot be -1, since then . Thus and it follows that .∎
Note that the variant of Euclid’s proof of the infinitude of primes used in the proof of Theorem 1 does not work for Theorem 2, since we cannot conclude that an integer has a factor of the same kind.
References
- 1 Apostol, T Introduction to Analytic Number Theory
, Springer 1976.