308
правок
Изменения
м
→Теорема о НОД периодов
==Теорема о НОД периодов==
Перед доказательством следующей теоремы докажем проверим пару интуитивно паонятных понятных утверждений.
{{Лемма
Требуется показать: <tex> s_i = 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]: \ \ i \equiv i' \pmod q,\ j \equiv j' \pmod q </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>.
Помимо того <tex> i \equiv j \pmod r </tex>, а в таком случае верно и <tex> i' \equiv j' \pmod r </tex>.
Теперь воспользуемся следующим фактом: если строка <tex> s </tex> имеет период <tex> r </tex>, то <tex> i \equiv j \pmod r \ \Rightarrow\ s_i = s_j </tex> (действительно, без ограничения общности можем сказать, что <tex> i \leqslant j </tex>, и исходя из чего можем этого выстроить цепочку равенств <tex> s_i = s_{i + r},\ \ s_{i + r} = s_{i + 2r},\ \ \dots \ , \ s_{j - r} = s_j </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>.
