Standard proof of infinitude of prime numbers (due to Euclid) goes as follows:
Assume, to the contrary, that there were only finitely many primes, say are all of them. Then, consider the number . We ask whether is prime or not. Well, since is strictly bigger than all of the numbers , by assumption cannot be prime (because all the primes are assumed to be ). So must be composite. But then a prime factor of must be for some with . Now observe that divides both and , and so divides the difference . We have shown that divides 1, and this is clearly a contradiction (because every prime is strictly larger than 1).
Let’s show another proof of infinitude of prime numbers using Fermat Numbers. For each we define . We call the n-th Fermat number. The idea is to show any two Fermat numbers are pairwise relatively prime. Why would this show infinitude of primes? Because if two numbers are pairwise relatively prime, they have distinct prime factors. And since there are infinitely many Fermat numbers, if every pair of them were relatively prime, then clearly we would generate infinitely many primes.
So it remains to show that for every with . Let . Observe that
Using the factorization , we know divides . So the above equation implies that divides . On the other hand, we have
Thus, divides . But divides . Thus, divides . By definition of , we know divides , and . Since divides , it follows that also divides . But then divides the difference . We have shown that divides . Since Fermat numbers are odd, their greatest common divisor must also be odd, hence is odd. We conclude that . This precisely shows that , as desired.