May 17, 2020
Let denote the set of strings consisting of just ’s whose length is a multiple of ; i.e.
Clearly, each is regular. Additionally, recall that if and are regular languages, then the intersection and the complement are regular.
By the fundamental theorem of arithmetic, a number is a power of exactly when is the only prime number that divides it, so if there were finitely many primes , then the set
of strings of ’s whose length is a power of is regular as is equal to the intersection of (finitely many) regular languages.
However, we can show is not regular by using the pumping lemma. For , then if we let , then and . If for strings with and , then as , , and , then . Additionally, as and , then so
Therefore, we have , so the length of cannot be a power of two and thus . Thus, by the pumping lemma, is not regular so there must be infinitely many primes.
This post was adapted from u/JoshuaZ1’s comment thread in r/math on different ways of proving the infinitude of primes.