308
правок
Изменения
м
→Свойства периода
Перед доказательством следующей теоремы сначала докажем пару интуитивно понятных леммутверждений.
{{Лемма
Помимо того <tex> i \equiv j \pmod r </tex>, тогда верно и <tex> i' \equiv j' \pmod r </tex>.
Теперь, поскольку <tex> w </tex> имеет период <tex> q </tex>, имеет имеют место равенства <tex> s_i = s_{i'}\ </tex> и <tex>\ s_j = s_{j'} </tex>. Поскольку <tex> v </tex> имеет период <tex> r </tex>, верно <tex> s_{i'} = s_{j'} </tex>. Тогда и <tex> s_i = s_j </tex>.
}}
|proof=Обозначим <tex> r = \gcd(p, q) </tex>. Доказательство будем вести индукцией по <tex> n = (p + q) / r </tex>.
* База
*: При <tex> n = 1 </tex> видно, что <tex> p = q = r </tex> и потому утверждение истинно.
* Переход
*: Заметим что теперь <tex> q \ne p </tex>(так как <tex> n \ne 1 </tex>), поэтому без ограничения общности можем сказать , что, <tex> q < p </tex>.
*: Пусть <tex> w = uv </tex>, где <tex> |u| = q </tex>.
*: По '''лемме 1 ''' <tex> v </tex> имеет период <tex> p - q </tex>, также <tex> v </tex> имеет период <tex> q </tex> как подстрока <tex> w </tex>. Теперь рассмотрим длину <tex> v </tex>:
*: <tex> |v| = |w| - q \geqslant (p - q) + q - r = (p - q) + q - \gcd(p - q, q) </tex>.
*: Тогда по предположению индукции получаем, что <tex> v </tex> также имеет период <tex> \gcd(p-q, q)</tex>. Поскольку <tex> \gcd(p-q, q) = \gcd(p, q) = r </tex>, можем сказать что <tex> v </tex> имеет период <tex> r </tex>.
*: Ещё заметим, что <tex> p - q \geqslant r </tex> (<tex> p > q </tex> и по свойствам НОД), поэтому <tex> |v| = |w| - q \geqslant (p + q - r) - q \geqslant q + (p - q) - r \geqslant q </tex>, тогда по '''лемме 2 ''' <tex> w </tex> имеет период <tex> r </tex>.
}}
