If a string $S$ can't itself be broken down into into repeating strings, then how can we prove that the no. of friends of $S$ is equals to its length?

20 Views Asked by At

Truly speaking the rule we have to prove is below which is taken from the Wikipedia page which doesn't gives its proof.

If $S$[a given string] is built up of several copies of the string $T$, and $T$ cannot itself be broken down further into repeating strings, then the number of friends of $S$ (including $S$ itself) is equal to the length of $T$.

Here, friend of a string $S$ is the set of strings which are identical to $S$ when it's end point are joined.

Wikipedia used this fact to prove Fermat's little theorem but didn't gave any proof of it.

1

There are 1 best solutions below

0
On

Consider the friends of $T$. Since $T$ is not composed of repeating strings, each unit shift of $T$ will be distinct, so $T$ has as many friends as the the length ($:=L$) of $T$. Use a subscript on $T$ to denote the number of unit shifts for each friend of $T$, noting $T=T_0=T_L$.

Now the friends of $S$ will be composed of copies of these friends of $T$. As such there are only $L$ distinct friends of $S$, since $S_L=S$.