Prove that the language of unary not-prime numbers satisfies the Pumping Lemma
Let $w \in \mathrm{PRIME}'$ with $|w| \geq 5$. Distinguish two cases.


$|w|$ is even -- in that case, choose $x = \varepsilon$, $y = aa$ and $z = a^{|w|-2}$. Then, for all $i\geq 0$, we have $|xy^iz|$ is even and greater than two, as $|z| \geq 3$, and therefore not prime; $xy^iz \in \mathrm{PRIME}'$.
$|w|$ is odd -- in this case, we can not verify the pumping property. This can be seen as follows.

We have

$\quad \forall m \geq 1.\, \exists n \geq m.\, \forall 1 &lt; k \leq m.\, \gcd(k, n-k) = 1 \qquad (\star)$

that is for every assumed pumping length $m$, there is a longer word $a^n$ which you can not separate into $a^k$ and $a^{n-k}$ with $k \leq m$ (note that $k=1$ trivially violates the pumping property) so that $k$ and $n-k$ share a divisor. Therefore, we can invoke Dirichlet's theorem for every possible separation, which yields that there are (infinitely many) primes you get by $(n-k) + ik$. So we can't find a pumpable split of $a^n$, and thus the pumping property is violated for $a^n$, which is enough to "contradict" the lemma.

$(\star)$ can be shown by contradiction. Pick $n&gt;m$ non-prime so that $n$ has no prime factor $\leq m$, e.g. $n = p^2$ for $p\geq m$ prime. Assume there was a $1&lt;k\leq m$ so that some $1&lt;d\leq k$ divided both $k$ and $n-k$, i.e. $k = id$ and $n-k = jd$ for some natural $i,j$. But then, $n = (i+j)d$, i.e. $d \leq m$ divides $n$, which contradicts the choice of $n$.