308
правок
Изменения
м
→Свойства периода
*: По лемме 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\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>.
