=

1. Assume that L is accepted by a FA with n states, for some n.
2. Choose a suitable string . This choice would depend on n.
   Let where n is a prime.
3. Break up z in uvw such that and . The break up of z must be general.
   

   Let
   for and .

4. Since , , for all . Use an appropriately chosen i to generate a string outside L. Your argument should take into account all possible valid break ups of z.
   

   That is, .
   is a prime, for all .
   Choose .
   Then, is also a prime, a contradiction.
   is not regular.

Step 2 and 4 are your choices, step 3 is adversary's choice.