Pumping Lemma Example 3

1. We don't know m, but assume there is one.

2. Choose a string w = aⁿ where n is a prime number and |xyz| = n > m+1. (This can always be done because there is no largest prime number.) Any prefix of w consists entirely of a's.

3. We don't know the decomposition of w into xyz, but since |xy| m, it follows that |z| > 1. As usual, |y| > 0,

4. Since |z| > 1, |xz| > 1. Choose i = |xz|. Then |xyⁱz| = |xz| + |y||xz| = (1 + |y|)|xz|. Since (1 + |y|) and |xz| are each greater than 1, the product must be a composite number. Thus |xyⁱz| is a composite number.