# Recitation 20

In this recitation, I defined greatest common divisor and its relation. Most importantly, I proved the following theorem.

The set of all integer combinations of a and b is equal to the set of all multiples of gcd(a,b).

The significance of the theorem is that it shows the regularity of the set (the set of all integer combinations) that seems chaotic at first sight.

I followed this theorem with an alternative proof of the infinitude of primes. Here is the outline of the proof.

Let a_n=2^{2^n}+1. In this sequence, every two terms are relatively prime, because a_m divides a_n-2 if m<n. Hence if we choose a prime factor for each term. Those primes are distinct. Hence we have infinitely many primes.