[Solved]: Pumping Lemma for $L = left { a^{c}mid text{c is a composite number} right }$

Let $p$ be the pumping length, and choose a prime $q > p$. The word $a^{q^2}$ is in $L$, and so it can be written as $a^{q^2} = uvwxy$ so that $|vwx| leq p$, $|vx| geq 1$, and $uv^iwx^iy in L$ for all $i geq 0$. If $|vx| = ell$ then $1 leq ell leq p$, and for all $i geq 0$, $q^2 + (i-1)ell$ is composite. Since $ell leq p$ and $q$ is prime, $(q^2,ell) = 1$, and so Dirichlet’s theorem about primes in arithmetic progressions shows that for infinitely many $i geq 0$, $q^2 + (i-1)ell$ is prime. We have reached a contradiction. An easier argument uses Parikh’s theorem, which states that a unary language (a subset of $a^*$) is context-free iff it is regular. In particular, it is enough to show that $L$ isn’t regular. Since the complement of a regular language is regular, it’s enough to show that $overline{L} = { a^k : k text{ is prime}}$ is not regular. It is easier to use the pumping lemma for this language. Given a pumping length $p$, choose a prime $q > p$. As before, there must exist $ell leq p$ so that $q + (i-1)p$ is prime for all $i geq 0$. However, for $i = q+1$ we get $q + (i-1)p = q + qp = q(p+1)$, which isn’t prime.