308
правок
Изменения
→Теорема о НОД периодов
{{Лемма
|about=1
|statement= Пусть строка <tex> s </tex> имеет периоды <tex> p </tex> и <tex> q </tex>, причём <tex> q < p < q \leqslant |s| </tex>. Тогда суффикс и префикс <tex> s </tex> длины <tex> |s| - q </tex> имеют период <tex> p - q </tex>.
|proof= Покажем истинность утверждения про префикс; с суффиксом доказательство аналогичное.
Требуется показать: <tex> s_i = s_j \ (j = i + r,\ 1 \leqslant i, j \leqslant n) </tex>.
Зафиксируем <tex> i </tex> и <tex> j </tex>. Заметим, что поскольку <tex> |v| \geqslant q </tex> , отрезок <tex> [h, k] </tex> содержит по меньшей мере <tex> q </tex> целых чисел, так что найдутся <tex> i',\ j' \in [h, k]: \ \ i \equiv i' \pmod q,\ j \equiv j' \pmod q ,\ i \ne j </tex>.
С учётом <tex> q </tex> <tex dpi=90>\,\vdots\, </tex> <tex> r </tex> можем написать <tex> i \equiv i' \pmod r,\ j \equiv j' \pmod r </tex> <ref>[[Сравнения,_система_вычетов,_решение_линейных_систем_по_модулю#Свойства сравнений | Свойство сравнений (№8)]]</ref>.
|author=Фин и Вильф
|proof=Обозначим <tex> r = \gcd(p, q) </tex>. Доказательство будем вести индукцией по <tex> n = (p + q) / r </tex>.
В случае <tex> p = q </tex> видим что <tex> n = 2 </tex>, что соответствует базе, в то время как при <tex> p \ne q </tex> выполнено <tex> p, q > \gcd(p, q) </tex>, так что <tex> n > 2 </tex>.
* База
*: При <tex> n = 2 </tex> видно, что Истинность утверждения следует из <tex> p = q = r </tex> и потому утверждение истинно.
* Переход
*: Заметим В силу того, что теперь <tex> q p \ne p q </tex> (так как , без ограничения общности будем считать <tex> n > 2 q < p </tex>)(вообще говоря, потому без ограничения общности считаем исходя из свойств НОД можно дать более строгую оценку: <tex> p - q < p \geqslant r </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 - r) - q \geqslant (p - q) + q - r = (p - q) + q - \gcd(p - q, q) </tex>.
*: Таким образом Ещё заметим, что для периодов <tex> p - q,\ q </tex> будет меньшее <tex> n </tex>, нежели чем для <tex> p,\ q </tex>, поскольку <tex> \gcd(p-q, q) = \gcd(p, 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| \geqslant (p - q) + q - r \geqslant q </tex>, в следствие чего по '''лемме 2''' <tex> w </tex> имеет период <tex> r </tex>.
}}
