- We don't know m, but assume there is one.
- Choose a string w = a
^{n}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. - We don't know the decomposition of w into xyz, but since |xy|
m, it follows that |z| > 1. As usual, |y| > 0,
- Since |z| > 1, |xz| > 1. Choose i = |xz|.
Then |xy
^{i}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^{i}z| is a composite number.

Copyright © 1996 by David Matuszek

Last modified Feb 20, 1996