148
правок
Изменения
→Свойства периода
Пусть Длина строки равна <tex>n</tex>. Тогда из определения периода имеем, что<br/>
<tex>\forall i = 1 \ldots n - k</tex>, <tex>\alpha [i] = \alpha[i + k]</tex>.<br/>
Это вернео верно для всех таких <tex>i</tex>, значит получаем <br/>
<tex>\alpha [i] = \alpha[i + k]</tex>.<br/>
<tex>\alpha [i + k] = \alpha[i + 2k]</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>.
