Concatenation of strings

Question

We have two strings A and B. We have to find if for some n,m A concatenated n times equals B concatenated m times or not. I have made an interesting observation but am unable to prove it.It appears that this can happen if and only if AB=BA

Answer 1

Hint. Show that $A^n = B^m$ implies that $A = C^i$ and $B = C^j$.

Answer 2

Let $A,B\in\Sigma^*$ be nonempty(!) words over the alphabet $\Sigma$.

Assume $AB=BA$. Let $n=|B|, m=|A|$. Then by looking at the first $nm$ symbols of $A^nB^m=B^mA^n$ we find $A^n=B^m$.

Assume $A^n=B^m$ with $n,m\ge 1$. If $n=1$ then $AB=B^{m+1}=BA$ and we are done. If $m=1$ then $AB=A^{n+1}=BA$ and we are done. So we may assume $n,m\ge 2$. Then the words $B^{m+1}=BA^n$ and $A^{n+1}=AB^m$ have $A^n=B^m$ as common prefix of length at least $m|B|=n|A|\ge 2\max\{|A|,|B|\}\ge |A|+|B|$. Therefore we have equality for the prefix of length $|A|+|B|$, i.e. $AB=BA$.