**From S. Tringali. link** Let be a set and denote by the free monoid on , which we write, as usual, in multiplicative notation. Let be the identity element of and the function mapping a word to its length (here, means the non-negative integers). Then, pick .

1. Prove that for every there exists at most one pair such that and .

2. Prove the following: If and are such that , then there exists such that and .

**Proof.**

1. If and then hence .

2. for . By symmetry wlog and .

It must be for some .

So , then , right multiply by to get .

That is .

From this we have .

Now, since we set and observe by induction that

if then and the thesis follows.

Otherwise let . There must be a word s.t. .

Observe .

Apply induction hypothesis we see that there must be a word and integers s.t. and .

Hence and . We pick the longest such .

From it must be , since otherwise we pick against the maximality of .

Moreover if we set observe and denote by such a number.

is a multiple of both and .

Since and we picked the longest , there cannot be a smaller such , since otherwise we pick .

This imply , that is and .**Q.E.D.**