How to prove that a string is made up of subsequences occurring some arbitrary number of times using concatenation?
Let us first state the theorem that we are trying to prove.

Theorem. Let $w \neq \epsilon$ be a word. Then $w^2 = xwy$ for $x,y \neq \epsilon$ if and only if $w = z^p$ for some $p &gt; 1$.

Proof. Let us first suppose that $w = z^p$ for some $p &gt; 1$. Then $w^2 = z^{2p} = zwz^{p-1}$, where $z,z^{p-1} \neq \epsilon$.

In the other direction, write $w = w_1w_2$, where $|xw_1| = |w_2y| = |w|$. Since $x,y \neq \epsilon$, we see that $|w_1|,|w_2| &lt; |w|$. We have $ww = xw_1w_2y$ implies that $w = xw_1 = w_2y$, and so $x = w_2$ (since $|x| = |w|-|w_1| = |w_2|$). In other words, $w = w_2w_1$.

Now let $w = \sigma_0 \ldots \sigma_{n-1}$, and let $|w_2| = m$. Note that since $|w_1|,|w_2| &lt; n$, we have $0 &lt; m &lt; n$. The equality $w = w_2w_1$ implies (check!) that $\sigma_i = \sigma_{i+m \bmod{n}}$. Let $g$ be the GCD of $m$ and $n$; note that $g &lt; n$. It is known that $g = am + bn$ for some integers $a,b$, and so $\sigma_i = \sigma_{i+bm \bmod{n}} = \sigma_{i+g \bmod{n}}$. Since $g \mid n$, this implies that $w = (\sigma_1 \ldots \sigma_g)^{n/g}$, where $n/g &gt; 1$.