# 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. Hence if we choose a prime factor for each term. Those primes are distinct. Hence we have infinitely many primes.