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