euclid's article from wiki

Main article: Euclid's theorem
There are infinitely many prime numbers. The oldest known proof for this statement, sometimes referred to as Euclid's theorem, is due to the Greek mathematician Euclid. Euclid states the result as "there are more than any given [finite] number of primes", and his proof is essentially the following:
Consider any finite set of primes. Multiply all of them together and add 1 (see Euclid number). The resulting number is not divisible by any of the primes in the finite set we considered, because dividing by any of these would give a remainder of 1. Because all non-prime numbers can be decomposed into a product of underlying primes, then either this resultant number is prime itself, or there is a prime number or prime numbers which the resultant number could be decomposed into but are not in the original finite set of primes. Either way, there is at least one more prime that was not in the finite set we started with. This argument applies no matter what finite set we began with. So there are more primes than any given finite number. (Euclid, Elements: Book IX, Proposition 20)
This previous argument explains why the product P of finitely many primes plus 1 must be divisible by some prime (possibly itself) not among those finitely many primes.
The proof is sometimes phrased in a way that falsely leads some readers to think that P + 1 must itself be prime, and think that Euclid's proof says the prime product plus 1 is always prime. This confusion arises when the proof is presented as a proof by contradiction and P is assumed to be the product of the members of a finite set containing all primes. Then it is asserted that if P + 1 is not divisible by any members of that set, then it is not divisible by any primes and "is therefore itself prime" (quoting G. H. Hardy[10]). This sometimes leads readers to conclude mistakenly that if P is the product of the first n primes then P + 1 is prime. That conclusion relies on a hypothesis later proved false, and so cannot be considered proved. The smallest counterexample with composite P + 1 is
(2 × 3 × 5 × 7 × 11 × 13) + 1 = 30,031 = 59 × 509 (both primes).
Many more proofs of the infinity of primes are known. Adding the reciprocals of all primes together results in a divergent infinite series:
The proof of that statement is due to Euler. More precisely, if S(x) denotes the sum of the reciprocals of all prime numbers p with p ≤ x, then
S(x) = ln ln x + O(1) for x → ∞.
Another proof based on Fermat numbers was given by Goldbach.[11] Kummer's is particularly elegant[12] and Harry Furstenberg provides one using general topology.[13]
Not only are there infinitely many primes, Dirichlet's theorem on arithmetic progressions asserts that in every arithmetic progression a, a + q, a + 2q, a + 3q, … where the positive integers a and q are coprime, there are infinitely many primes.