Show that L = a^n n is a prime number is not a regular language.

We use the pumping lemma for regular languages: if L is regular, there is a constant p such that every string w in L with |w| ≥ p can be split as w = xyz with |xy| ≤ p and |y| ≥ 1, where xyⁱz is in L for every i ≥ 0.

Proof by contradiction

Assume L = { aⁿ | n is prime } is regular, and let p be its pumping length.

Choose a prime n ≥ p + 2 and let w = aⁿ, which is in L and has |w| ≥ p.

Split w = xyz with |xy| ≤ p and |y| = k ≥ 1. Then all three parts are strings of a's, and |xz| = n − k.

Pump with i = n − k. The string xy^(n−k)z has length

|xz| + (n − k)·|y| = (n − k) + (n − k)k = (n − k)(k + 1).

Both factors are greater than 1:

• k + 1 ≥ 2, because k ≥ 1;
• n − k ≥ 2, because k ≤ p and n ≥ p + 2.

So the length (n − k)(k + 1) is a product of two numbers greater than 1, which means it is not prime. Hence xy^(n−k)z is not in L, which contradicts the pumping lemma.

Therefore L is not regular.