Изменения

Пусть строка равна <tex> \alpha </tex>.<br/>Доказательство будем вести по парам <tex>(p, q)</tex>, где <tex> p \geqslant q </tex>, а <tex> (p , q) + 1 = \begin{cases} (p, q + 1), & q < p;\\(p + 1, 1), & q = p.\end{cases}</tex><br/>Для <tex> (1, 1) </tex> утверждение очевидно.<br/>Пусть верно для <tex> (p, q ) - 1 < (p, q)</tex>, тогда.<br/> Докажем, что верно для <tex>(p, q)</tex>. Для <tex>\forall i = 1 \ldots n - p</tex>, <tex>\alpha [i] = \alpha[i + p] = \alpha[i + q]</tex>.<br/>

Получили новый период длины <tex>|p - q|</tex>. Пусть теперь Из предположения известно, что НОД<tex>p = max(p - q, q)</tex>{{---}} период строки, а но НОД<tex>q = min(p - q, q)</tex>.<br/>Будем повторять алгоритм сначала, пока <tex>p <> q=</tex>.Видно, что представленный алгоритм - это алгоритм Евклида. Значит при его завершении получим, что последний найденный период равен НОД<tex>(p, q)</tex>. Следовательно утверждение доказано.