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 .
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. .
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.