Why the language of unary primes isn't regular

Question

I have some difficulties proving that the language of unary primes ($L=\{1^p\mid p\text{ is prime}\}$) is not regular using the pumping lemma. Any suggestions?

Answer 1

This is one of the more difficult common applications of the pumping lemma, so I'll give you an outline to get you started.

Suppose $L$ is regular and let $k$ be the pumping length. Let $p$ be a big enough prime^* so $1^p\in L$, and write $a=1^r1^s1^t$, with $r+s\leq k$ and $s\geq 1$, so $t=p-r-s$. You need to find some $n$ such that $1^r(1^s)^n1^t\notin L$, i.e., such that $r+ns+t$ is not prime, which you can show by writing it as a product of two factors, both strictly bigger than $1$.

^* You'll certainly need $p>k$ to apply the pumping lemma, but you might need it to be bigger still, to guarantee that the factors are bigger than $1$.