148
правок
Изменения
→Свойства периода
|statement= Если у строки есть [[Основные определения, связанные со строками|период]] длины <tex>|k|</tex>, то у нее есть период длины <tex>|kx|</tex>, где <tex> x \in N</tex>.
|proof=
Пусть длина строки равна <tex>n</tex>, сама строка {{---}} <tex> \alpha </tex>.<br/>
Доказательство будем вести по индукции по числу <tex>x</tex>.<br/>
Для <tex> x = 1 </tex> утверждение очевидно.<br/>
|statement= Если у строки есть периоды длины <tex>|p|</tex> и <tex>|q|</tex>, то НОД<tex>(p, q)</tex> также является периодом этой строки.
|proof=
Пусть строка равна <tex> \alpha </tex>, а <tex> p > q </tex>, тогда<br/>
для <tex>\forall i = 1 \ldots n - p</tex>, <tex>\alpha [i] = \alpha[i + p] = \alpha[i + q]</tex>.<br/>
Значит для <tex>\forall i = q \ldots n - p</tex>, <tex>\alpha [i + q] = \alpha[i + p]</tex><br/>
