Primitive word and cyclic rotations

Definition. A word $$w \in \Sigma^*$$ is primitive if $$w=u^n \rightarrow n=1$$.

Is it true that a word is primitive if and only if its all cyclic rotations are dstinct?

Yes, this is true. The direct implication ($$\Rightarrow$$) is the hardest to prove, and you will need the following lemma: two words commute if and only if they are powers of the same word (R.C. Lyndon and M.P. Schützenberger, The equation a M = bncp in a free group, Michigan Math. J. 9 (1962) 289-298. Or in this: H. Petersen, On the language of primitive words, Theor. Comp. Sci., 1996 https://doi.org/10.1016/0304-3975(95)00098-4). The rest of the proof should be straightforward enough.

• Thank you, can you give me the other implication? – asv Jan 16 '20 at 10:20
• By contraposition: assume the word is not primitive, then explicitely construct two cyclic permutations which are equal. – integrator Jan 16 '20 at 10:22
• Ok, just shift by $|u|$, right? – asv Jan 16 '20 at 10:26