Изменения

|statement= Пусть строка <tex> w s </tex> имеет периоды <tex> p </tex> и <tex> q </tex>, причём <tex> p < q \leqslant |ws| </tex>. Тогда суффикс и префикс <tex> w s </tex> длины <tex> |ws| - q </tex> имеют период <tex> p - q </tex>.

Требуется показать что <tex> s_i = s_{i+p-q} \ \ (i = 1,\dots,n-p; \ n=|s|) </tex>

Поскольку <tex> w s </tex> имеет период <tex> p </tex>, выполнено <tex> s_i = s_{i+p} </tex> Также <tex> w s </tex> имеет период <tex> q </tex> и из ограничений на <tex> i </tex> верно <tex> 1 \leqslant i + p - q \leqslant n - q </tex>, поэтому <tex> s_{i+p-q} = s_{i+p} </tex>

Требуется показать: <tex> a_i s_i = a_j s_j \ (j = i + r,\ 1 \leqslant i, j \leqslant n) </tex>. Заметим, что поскольку <tex> |v| \geqslant q </tex>, то отрезок <tex> [h, k] </tex> содержит ровно <tex> q </tex> целых чисел, так что найдутся <tex> i',\ j' \in [h, k] </tex> такие, что <tex> i \equiv i' \pmod q,\ j \equiv j' \pmod q </tex>. Так как <tex> q|r </tex>, можем написать <tex> i \equiv i' \pmod r,\ j \equiv j' \pmod r </tex>.  Помимо того <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>.

|statement= Если у строки длины <tex>nw</tex> есть периоды <tex>p</tex> и <tex>q</tex>, где <tex>|w| \geqslant p + q - НОДGCD(p, q) \leqslant n</tex>, то НОД<tex>(p, q)</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> 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) + q - r \geqslant q </tex>, тогда по лемме 2 <tex> w </tex> имеет период <tex> r </tex>.