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