Свойства операции остатка от деления по модулю:
\(\forall a, b \in \mathbb{N}_{0}, m \in \mathbb{N}\):
- \(0 \le { \left( a \mod m \right) } \le m-1 \)
- \({ \left( a \mod m \right) } \mod m = a \mod m \)
- \(\left( a \cdot b \right) \mod m\) \(=\) \(\left( \left( a \mod m \right) \cdot \left( b \mod m \right) \right) \mod m\).
Лемма “О конечности модулярно-степенной последовательности”
\(a_{0}\) \(=\) \(1\) \(=\) \(a^{0}\) \(=\) \(a^{0} \mod m\),
\(a_{1}\) \(=\) \(a\) \(=\) \(a^{1}\) \(=\) \(a^{1} \mod m\),
\(a_{i}\) \(=\) \(\left( a_{i-1} \cdot a \right) \mod m\) \(=\) \(a^{i} \mod m\), \(i = \overline{2, m}\).
Тогда для данной последовательности справедливо условие повторения:
\(\exists i \in {\mathbb{N}_{0}}\), \(j \in \mathbb{N}\), \(0 \le i < j \le m\):
\(a_{i}\) \(=\) \(a_{j}\).
Периодичность возведения в степень по модулю
Продлим ранее рассматриваемую последовательность до бесконечности, и далее будем рассматривать только полученную последовательность \(\{ a_{i} \}_{i=0}^{+\infty}\), определённую по закону:
\(a_{0}\) \(=\) \(1\) \(=\) \(a^{0}\) \(=\) \(a^{0} \mod m\),
\(a_{1}\) \(=\) \(a\) \(=\) \(a^{1}\) \(=\) \(a^{1} \mod m\),
\(a_{i}\) \(=\) \(\left( a_{i-1} \cdot a \right) \mod m\) \(=\) \(a^{i} \mod m\), \(i = \overline{2, +\infty}\), где \(m \in \mathbb{N}\), \(m \ge 2\) – некоторый модуль, \(a \in \{ 0, 1, \ldots, m-1 \}\).
Назовём эту последовательность модулярно-степенной последовательностью с модулем \(m\) и базисным числом \(a\).
По лемме о конечности модулярно-степенной последовательности (далее – МСП), имеем, что для первых \(m\) элементов справедливо условие повторения: \(\exists i \in {\mathbb{N}_{0}}\), \(j \in \mathbb{N}\), \(0 \le i < j \le m\): \(a_{i}\) \(=\) \(a_{j}\).
Итак, пусть заданы индексы \(i\) и \(j\), для которых это условие выполнено. Из определения последовательности следует, что \(a_{i+1} = \left(a_{i} \cdot a \right) \mod m\), и аналогично \(a_{j+1}\) \(=\) \(\left(a_{j} \cdot a \right) \mod m\). Однако поскольку \(a_{i}\) \(=\) \(a_{j}\), \(a_{j+1}\) \(=\) \(\left(a_{j} \cdot a \right) \mod m\) \(=\) \(\left(a_{i} \cdot a \right) \mod m\) \(=\) \(a_{i+1}\). Итак, \(a_{i+1}\) \(=\) \(a_{j+1}\). Аналогично можно показать, что \(a_{i+2}\) \(=\) \(a_{j+2}\), \(a_{i+3}\) \(=\) \(a_{j+3}\), и в общем случае \(\forall t \in \mathbb{N}_{0}\) \(a_{i+t}\) \(=\) \(a_{j+t}\).
Итак, пусть задана МСП \(\{ a_{i} \}_{i=0}^{+\infty}\) с модулем \(m\) и базисным числом \(a\).
Теорема “О периоде МСП”
Пусть задана МСП \(\{ a_{i} \}_{i=0}^{+\infty}\) с модулем \(m\) и базисным числом \(a\), а также определены \(i\) и \(j\) – начало периода и первая точка повторения соответственно. Тогда период \(p\) данной последовательности существует, и вычисляется по формуле \(p = j – i\).
Возьмём один из фактов из приведённых выше рассуждений: \(\forall t \in \mathbb{N}_{0}\) \(a_{i+t}\) \(=\) \(a_{j+t}\). Зададим число \(p = j-i\), и покажем, что оно является периодом последовательности.
Случай \(a_{i+t}\) \(=\) \(a_{i+p+t}\) очевиден, поскольку \(a_{i}\) \(=\) \(a_{j}\). Рассмотрим равенство \(a_{i+t} = a_{i+p+t}\) при \(t = kp\), \(k = \overline{0, +\infty}\):
\(a_{i} = a_{i+p}\),
\(a_{i+p} = a_{i+2p}\),
\(a_{i+2p} = a_{i+3p}\),
\(a_{i+3p} = a_{i+4p}\),
\(\ldots\),
\(a_{i+ \left( k-1 \right) p} = a_{i+kp}\),
\(\ldots\)
Очевидно, что \(a_{i}\) \(=\) \(a_{i+p}\) \(=\) \(a_{i+2p}\) \(=\) \(a_{i+3p}\) \(=\) \(\ldots\) \(=\) \(a_{i+kp}\) \(=\) \(\ldots\). Тогда \(\forall k_{0} \in \mathbb{N}_{0}\): \(a_{i} = a_{i+k_{0}p}\).
Далее, по определению последовательности мы имеем, что \(a_{i+1} = a_{i+k_{0}p+1}\), \(a_{i+2} = a_{i+k_{0}p+2}\), \(\ldots\) \(a_{i+p-1} = a_{i+k_{0}p+p-1}\), то есть: \(\forall t_{0} \in \{ 0, \ldots, p-1 \}\) \(a_{i+t_{0}} = a_{i+k_{0}p+t_{0}}\). Следовательно, по определению, число \(p\) является периодом модулярно-степенной последовательности. Теорема доказана.
Практическое применение, основная формула периода МСП
Исходя из приведённой выше теории очевидно, что возведение в степень по модулю обладает свойством периодичности. Итак, пусть для некоторой МСП \(\{ a_{i} \}_{i=0}^{+\infty}\) с модулем \(m\) и базисным числом \(a\) найдены начало периода \(i\) и первая точка повторения \(j\). Тогда период данной последовательности, как было показано в теореме, будет равен \(p = j-i\). Найдём первые \(j\) элементов последовательности:
\(a_{0}\) \(=\) \(1\) \(=\) \(a^{0}\) \(=\) \(a^{0} \mod m\),
\(a_{1}\) \(=\) \(a\) \(=\) \(a^{1}\) \(=\) \(a^{1} \mod m\),
\(a_{k}\) \(=\) \(\left( a_{k-1} \cdot a \right) \mod m\) \(=\) \(a^{k} \mod m\), \(k = \overline{2, j-1}\), среди которых:
\(a_{i}\) \(=\) \(\left( a_{i-1} \cdot a \right) \mod m\) \(=\) \(a^{i} \mod m\).
Мы знаем, что при индексах, больших либо равных \(i\) элементы последовательности начнут повторять значения из уже найденных нами элементов. Следовательно…
Основная формула периода
Пусть задана МСП \(\{ a_{i} \}_{i=0}^{+\infty}\) с модулем \(m\) и базисным числом \(a\), началом периода \(i\) и периодом \(p\). Тогда для любой степени \(T \in \mathbb{N}_{0}\), \(T \ge i\) справедлива формула:
\(a^{T} \mod m\) \(=\) \(a^{\left( T-i \right) \mod p + i} \mod m\).
В случае \(0 \le T < i\) значение \(a^{T}\) берём из МСП: \(a_{T}\) \(=\) \(a^{T}\).
Эта формула является следствием из приведённой теоремы. Поскольку при возведении в степень начиная с индекса начала периода \(i\) элементы с индексами \(i+t\) и \(i+kp+t\), \(\forall k \in \mathbb{N}_{0}\), \(\forall t \in \{0, \ldots, p-1 \}\) совпадают, вычитая от степени \(T \ge i\) начало периода \(i\) и беря полученное число по модулю \(p\) и прибавляя к нему \(i\), мы возвращаем его в рамки элементов \(a_{k}\) \(=\) \(\left( a_{k-1} \cdot a \right) \mod m\) \(=\) \(a^{k} \mod m\), \(k = \overline{i, i+p-1}\).
Таким образом находя индекс начала периода и сам период путём построения соответствующих элементов МСП для некоторого базисного числа \(a\), получим возможность возводить это число \(a\) в любую неотрицательную целую степень по модулю мгновенно. По крайней мере, с помощью вычислительного устройства.
Также можно провести обобщения возведения в степень по модулю до произвольного целого числа \(A \in \mathbb{Z}\):
\(A \mod m = sign(A) \cdot a\), \(a \ge 0\), тогда \(\forall T \in \mathbb{N}_{0}\) \(A^{T} \mod m = \left( sign(A)^{\left( T \mod 2 \right) } \cdot a^{\left( \left( T-i \right) \mod p + i \right)} \right) \mod m\).
Степенные сравнения
Полученную информацию можно использовать для решения степенных сравнений вида:
\(a^{x} \equiv b \left( \mod m \right)\), где \(x \in \mathbb{N}_{0}\) – неизвестная переменная, \(a\), \(b\) \(\in \mathbb{N_{0}}\) – известные коэффициенты, \(m\) – модуль сравнения.
Построим МСП \(\{ a_i \}_{i=0}^{m}\):
\(a_{0}\) \(=\) \(1\) \(=\) \(a^{0}\) \(=\) \(a^{0} \mod m\),
\(a_{1}\) \(=\) \(a\) \(=\) \(a^{1}\) \(=\) \(a^{1} \mod m\),
\(a_{i}\) \(=\) \(\left( a_{i-1} \cdot a \right) \mod m\) \(=\) \(a^{i} \mod m\), \(i = \overline{2, m}\).
Эта процедура займёт \(O \left( m \right)\) операций. Найдём первую точку повторения \(i\) и период \(p\), что тоже займёт \(O \left( m \right)\).
С помощью МСП перебираем \(x\) из множества \(\{ 0, 1, \ldots, i+p-1 \}\), и соответствующие им \(a_x = a^x\). Пусть \(i\) – первая точка повторения, \(p\) – период, и пусть \(x_{0}\) – частное решение сравнения из множества \(\{ 0, 1, \ldots, i+p-1 \}\), найденное в результате перебора. Если \(x_{0} < i\), то множество ответов пополняем значением \(x_{0}\), иначе если \(x_{0} \ge i\), множество ответов пополняем значениями \(x_{0}+kp\), \(k \in \mathbb{N}_{0}\).
Возведение в двойную степень
Исходя из похожих рассуждений, данную теорию можно усилить до случая возведения в s-арную двойную/умноженную степень:
Пусть задана первая степень/множитель степени \(s \in \mathbb{N}\), некоторый модуль \(m \in \mathbb{N}\), \(m \ge 2\) и некоторое число \(a \in \{ 0, 1, \ldots, m-1 \}\). Построим последовательность элементов:
\(a_{0}\) \(=\) \({ \left( a^s \right) }^0 \mod m\) \(=\) \(a^{s \cdot 0} \mod m\) \(=\) \(a^{0} \mod m\) \(=\) \(1\),
\(a_{1}\) \(=\) \({ \left( a^{s} \right) }^1 \mod m\)\(=\) \(a^{s \cdot 1} \mod m\) \(=\) \(a^{s} \mod m\),
\(a_{i}\) \(=\) \(\left( a_{i-1} \cdot a^{s} \right) \mod m\) \(=\) \({{\left( a^s \right)}^i} \mod m\) \(=\) \(a^{si} \mod m\), \(i = \overline{2, +\infty}\).
Для этой последовательности по аналогии доказывается наличие двух одинаковых элементов среди первых \(m\) из них, вводятся понятия начала периода \(i\), первой точки повторения \(j\) и периода \(p\):
\(i\), \(j\) – наименьшие такие, что: \(i \in {\mathbb{N}_{0}}\), \(j \in \mathbb{N}\), \(0 \le i < j \le m\), \(a_{i}\) \(=\) \(a_{j}\);
\(p\): \(\forall k \in \mathbb{N}_{0}\), \(\forall t \in \{0, \ldots, p-1 \}\) \(a_{i+t}\) \(=\) \(a_{i+kp+t}\).
Также справедливой останется основная формула периода, но с изменениями: \(\forall T \ge i\), \(T \in \mathbb{N}_{0}\),
\({\left( a^s \right) }^{T} \mod m\) \(=\) \(a^{sT} \mod m\) \(=\) \({ \left( a^s \right) }^{\left( T-i \right) \mod p + i} \mod m\) \(=\) \({a^{s \left( {\left( T-i \right) \mod p + i} \right) }} \mod m\).
Возведение в повторную степень
Расмотрим ещё один вид модулярных последовательностей – последовательности с повторными степенями.
Пусть заданы модуль \(m \in \mathbb{N}\), \(m \ge 2\), базисное число последовательности \(a \in \{ 0, \ldots, m-1 \}\), и количество повторений степени \(r \in \mathbb{N}\), \(r \ge 2\). Тогда модулярной последовательностью с модулем \(m\), базисным числом \(a\) и повторной степенью \(r\) назовём последовательность \(\{ a_{i} \}_{i = 0}^{+\infty}\), определённую следующим образом:
\(a_{0}\) \(=\) \(a \mod m\),
\(a_{i}\) \(=\) \(a_{i-1}^{r} \mod m\), \(i = \overline{1, +\infty}\).
Все предыдущие рассуждения так же переносятся на этот вид последовательностей. В этот раз приведём только конечный результат: если \(p\) – период последовательности с заданными параметрами \(m\), \(a\), \(r\) и \(i\) – начало этого периода, то: \(\forall T \ge i\), \(T \in \mathbb{N}_{0}\):
\(a_{T} = a_{(T-i) mod p+i}\).