Для понимания материалов настоящего раздела рекомендуется ознакомиться с разделом ((:modular МОДУЛЯРНАЯ АРИФМЕТИКА)). Сложность материалов раздела --- повышенная. ==Индекс (дискретный логарифм)== ~~TOC~~ === Первообразный корень == **Задача.** Найти длину цикла последовательности $ \{A^j \pmod{M} \}_{j=0}^{\infty} $ . Для случая простого модуля верхняя оценка для длины цикла дается ((:modular#теорема_ферма теоремой Ферма)): !!Т!! **Теорема [Ферма (малая)].** //Если// $ p_{} $ //простое и// $ A_{} $ //не делится// //на// $ p_{} $, //то// $$ A^{p-1} \equiv 1 \pmod{p} \ . $$ Примеры показывают, что для некоторых $ A_{} $ эта оценка достигается, а для других может быть уменьшена: $$ \begin{array}{ccl} \left\{3^j \pmod{17} \right\}_{j=0}^{\infty}&=& 1,\, 3,\, 9,\,10,\, 13,\, 5,\,15,\,11,\,16,\,14,\,8,\,7,\,4,\,12,\,2,\,6,\,1,\dots ; \\ \left\{4^j \pmod{17} \right\}_{j=0}^{\infty}&=& 1,\, 4,\,16,\, 13,\, 1,\,4,\dots ; \\ \left\{13^j \pmod{17} \right\}_{j=0}^{\infty}&=& 1,\,13,\, 16,\, 4,\, 1,\, 13 , \, 16,\, 4,\, 1,\, 13,\, 16,\dots ; \\ \left\{16^j \pmod{17} \right\}_{j=0}^{\infty}&=& 1,\,16,\, 1,\,16,\, 1,\, 16,\,1,\dots \end{array} $$ !!Т!! **Теорема 1.** //Если число// $ A_{} $ //не делится на простое// $ p>2 $, //то// $$ { . } \mbox{ либо } A^{(p-1)/2} \equiv 1 \pmod{p} \ , \quad \mbox{ либо } A^{(p-1)/2} \equiv -1 \pmod{p} \ . $$ **Доказательство.** Поскольку $ p_{} $ --- нечетное, то $ (p-1)_{} $ --- четное. Имеем $$A^{p-1} -1 =\left( A^{(p-1)/2} -1 \right) \left( A^{(p-1)/2} +1 \right) \ . $$ По теореме Ферма левое число делится на $ p_{} $, следовательно (по теореме 2 ☞ ((:numtheory#каноническое_разложение_числа ЗДЕСЬ)) ), по крайней мере один из сомножителей справа должен делиться на //простое// $ p_{} $. ♦ !!П!! **Пример.** Для $ p=17 $ имеем: $$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline A & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ \hline A^{(p-1)/2}\pmod{p} & 1 & 1 & -1 & 1 & -1 & -1 & -1 & 1 & 1 & -1 & -1 & -1 & 1 & -1 & 1 & 1 \\ \hline \end{array} $$ Видим, что половина чисел $ \{ 1, 2,\dots, 16 \} $ при отображении $ A^{8} \pmod{17} $ переходит в $ 1_{} $, а половина --- в $ 16 \equiv -1 \pmod{17} $. Ниже будет показано, что выявленная закономерность справедлива для любого простого $ p_{} $. ♦ Предыдущий результат допускает обобщение, которое предварим определением. **Чётностью** целого числа $ A_{} $ называется показатель степени $ 2_{} $ в ((:numtheory#каноническое_разложение_числа каноническом разложении)) этого числа[[parity (//англ.//) --- четность.]]: $$ \operatorname{prt}(A)=r \quad \iff \quad A \ \mbox{ делится на } \ 2^r,\ \mbox{ но не делится на } 2^{r+1} \quad \iff \quad A=2^rA_1,\ \mbox{ где }\ A_1 \mbox{ - нечетное } \ . $$ !!П!! **Пример.** $ \operatorname{prt}(A)=0 \ \iff \ A $ --- нечетное; $ \operatorname{prt}(28)=2 $, $ \operatorname{prt}(128)=7 $, $ \operatorname{prt}(368)= \qquad $ . !!Т!! **Теорема 2.** //Пусть число// $ p>2 $ //простое и// $ \operatorname{prt}(p-1)=r $, т.е. $ p-1=2^rq $, //где// $ q_{} $ --- //нечетное. Если число// $ A_{} $ //не делится на// $ p_{} $, //то// $$ { . } \mbox{ либо } \ A^{q} \equiv 1 \pmod{p} \ , \quad \mbox{ либо } \ A^{2^jq} \equiv -1 \pmod{p} $$ //для некоторого// $ j\in \{0,1,\dots,r-1 \} $. **Доказательство.** $$ \begin{array}{rcl} A^{p-1} -1 &=&\left( A^{(p-1)/2} +1 \right)\left( A^{(p-1)/2} -1 \right) = \\ &=&\left( A^{2^{r-1}q} +1 \right)\left( A^{2^{r-1}q} -1 \right)= \\ &=&\left( A^{2^{r-1}q} +1 \right)\left( A^{2^{r-2}q} +1 \right) \left( A^{2^{r-2}q} -1 \right) =\\ &=&\dots = \left( A^{2^{r-1}q} +1 \right)\times \dots \times \left(A^{2q}+1 \right) \left(A^q+1 \right)\left(A^q-1 \right) \ . \end{array} $$ Завершается доказательство теми же рассуждениями, что и доказательство теоремы 1. ♦ !!П!! **Пример.** Для $ p=41 $ имеем: $ r=\operatorname{prt}(40)=3,\ q=5 $ и $$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline A & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ \hline A^{q} \pmod{p} & 1 & & & -1 & & & & & & 1 & & & \\ \hline A^{2q} \pmod{p} & & -1 & & & -1 & & & -1 & -1 & & & & \\ \hline A^{4q} \pmod{p} & & & -1 & & & -1 & -1 & & & & -1 & -1 & -1 \\ \hline \end{array} $$ ♦ Наименьшее $ k_{}\in \mathbb N $, удовлетворяющее сравнению $ {A^k\equiv 1 \pmod{M}} $, называется **порядком** или **показателем** числа $ A_{} $ **по модулю** $ M_{} $. В случае, когда в контексте $ M_{} $ считается фиксированным, слова "по модулю $ M_{} $" опускают, и тогда порядок $ A_{} $ обозначают $ \operatorname{ord}(A) $: $$A^{\operatorname{ord}(A)}\equiv 1 \pmod{M},\ A^{\ell} \not\equiv 1 \pmod{M} \ npu \ \forall \ell\in \{1,\dots,\operatorname{ord}(A) -1 \} \ . $$ !!П!! **Пример.** При $ M=17 $: $$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline A & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ \hline \operatorname{ord} & 1 & 8 & 16 & 4 & 16 & 16 & 16 & 8 & 8 & 16 & 16 & 16 & 4 & 16 & 8 & 2\\ \hline \end{array} $$ При $ M=20 $ имеем: $$ \begin{array}{|c|c|c|c|c|c|c|c|c|} \hline A & 1 & 3 & 7 & 9 & 11 & 13 & 17 & 19 \\ \hline \operatorname{ord} & 1 & 4 & 4 & 2 & 2 & 4 & 4 & 2 \\ \hline \end{array} $$ !!Т!! **Теорема 3.** //Если// $ A^n \equiv 1 \pmod{M} $, то $ n_{} $ //делится на// $ \operatorname{ord} (A) $. //В частности,// $ \phi(M) $ //делится на// $ \operatorname{ord}(A) $ //для любого// $ A_{} $ //такого, что// $ \operatorname{HOD}(A,M)=1 $. **Доказательство.** Действительно, предположим, что не существует чисел $ \ell\in \mathbb N $, $ \ell< \operatorname{ord} (A) $ таких, что $ A^{\ell}\equiv 1 \pmod{M} $, но тем не менее что $ n_{} $ имеет ненулевой остаток при делении на $ \operatorname{ord} (A) $: $ n=\operatorname{ord} (A) \cdot q +r, \ 0 ♦ !!=>!! Для любого $ A_{} $ и $ n_{}>1 $ число $ \phi (A^n-1) $ делится на $ n_{} $. **Доказательство.** Число $ A_{} $ взаимно просто с числом $ M=A^n-1 $ и имеет порядок $ n_{} $ по модулю $ M_{} $ . Действительно, $ A^n \equiv 1 \pmod{A^n-1} $, но $ A^k-1 $ не делится на $ A^n-1 $ при $ k ♦ Итак, решение задачи, поставленной в начале пункта --- об оценке длины цикла последовательности $ \{A^j \pmod{M} \}_{j=0}^{\infty} $ --- сводится к задаче определения $ \operatorname{ord} (A) $, последнее число следует искать среди делителей $ \phi(M) $. Для простого модуля $ M=p>2 $ одним из таких делителей числа $ \phi(p)=p-1 $ является $ 2_{} $, и этот факт проявился в теореме 1. Очевидно, что при $ p>3 $ может существовать и делитель $ q\ne 2 $ числа $ p-1 $, что позволяет предполагать существование числа $ A\in \{1,2,\dots,p-1 \} $, имеющего порядок равный $ q_{} $. !!Т!! **Теорема 4.** //Если число// $ q_{} $ //является делителем числа// $ p-1 $, //то среди чисел// $$ 1,2,\dots,p-1 $$ //существует ровно// $ q_{} $ //чисел, удовлетворяющих сравнению// $$A^q \equiv 1 \pmod{p} \ .$$ **Доказательство.** Теорема Ферма утверждает, что сравнение $$x^{p-1}-1 \equiv 0 \pmod{p} $$ имеет $ p-1 $ решений: именно все числа $ x\in\{1,2,\dots,p-1\} $. Поскольку $ p-1 $ четно, то $$x^{p-1}-1=\left( x^{(p-1)/2} -1 \right) \left( x^{(p-1)/2} +1 \right) \ , $$ и из теоремы 3 раздела ☞ ((:modular#решение_нелинейных_сравнений РЕШЕНИЕ НЕЛИНЕЙНЫХ СРАВНЕНИЙ)) следует, что половина из чисел $ \{1,2,\dots,p-1\} $ удовлетворяет сравнению $ x^{(p-1)/2} \equiv 1 \pmod{p} $, а половина --- сравнению $ x^{(p-1)/2} \equiv -1 \pmod{p} $. Далее, если число $ q>2 $ --- произвольный делитель числа $ p-1 $, то $$x^{p-1}-1=\left( x^q -1 \right) \left( x^{(p-1)/q}+x^{(p-1)/q-1} + \dots + x +1 \right) \ , $$ и на основании той же теоремы сравнению $ x^{q} \equiv 1 \pmod{p} $ удовлетворяет ровно $ q_{} $ чисел множества $ \{1,2,\dots,p-1\} $. ♦ Выясним теперь вопрос о существовании цикла максимально возможной длины. Число $ \Lambda $ называется **первообразным корнем**[[В англоязычной литературе принято название primitive root.]] **по модулю** $ M_{} $, если $ \operatorname{ord} (\Lambda)=\phi(M) $. Это определение сходно по смыслу с определением ((:complex_num#корни_из_единицы первообразного комплексного корня из единицы)). В самом деле, первообразный корень из единицы степени $ n_{} $ определяется как такое решение уравнения $ z^n-1=0 $, которое не является решением уравнения $ z^k-1 = 0 $ при $ \forall k \in \{1,\dots,n-1\} $. Первообразный корень по модулю определяется как решение сравнения $ z^{\phi(M)}-1 \equiv 0 \pmod{M} $, которое не является решением сравнения $ z^k-1 \equiv 0 \pmod{M} $ при $ \forall k \in \{1,\dots,\phi(M)-1\} $. Для простого модуля $ M=p>2 $ число $ \Lambda $ является первообразным корнем тогда и только тогда, когда $ \operatorname{ord} (\Lambda)=p-1 $. !!П!! **Пример.** Согласно таблице приведенного выше примера первообразными корнями по модулю $ 17_{} $ будут числа $ 3,\, 5,\, 6,\, 7,\, 10,\, 11, 12, 14 $ . Тот же пример показывает, что для модуля $ M=20 $ первообразных корней не существует. ♦ Оказывается, что для простого модуля $ M=p>2 $ первообразный корень всегда существует. Как проверить, что число $ \Lambda $ является первообразным корнем по модулю $ p_{} $ ? На первый взгляд, кажется, что нужно проверить выполнение условия $ \Lambda^q \not\equiv 1 \pmod{p} $ для каждого делителя $ q_{} $ числа $ p-1 $. Так, при $ p=37 $ эта проверка заключается в: $$ \Lambda^2 \not\equiv 1 ,\ \Lambda^3 \not\equiv 1,\ \Lambda^4 \not\equiv 1,\ \Lambda^6 \not\equiv 1,\ \Lambda^{12} \not\equiv 1,\ \Lambda^{18} \not\equiv 1 \pmod{37} \ . $$ На самом же деле, достаточно проверить всего два из этих условий: $$ \Lambda^{12} \not\equiv 1,\ \Lambda^{18} \not\equiv 1 \pmod{37} \ , $$ поскольку для удовлетворяющего им числа $ \Lambda $ все остальные условия также будут выполнены. Эти рассуждения обобщаются следующим утверждением. !!Т!! **Теорема 5.** //Если ((:numtheory#каноническое_разложение_числа каноническое разложение)) числа// $ p-1 $ //имеет вид//: $$ p-1=p_1^{{\mathfrak m}_{_1}}p_2^{{\mathfrak m}_{_2}}\times \dots \times p_{\mathfrak r}^{{\mathfrak m}_{_{\mathfrak r}}} \ , $$ //то для того чтобы число// $ \Lambda $, //не делящееся на// $ p_{} $, //было первообразным корнем по модулю// $ p_{} $, //необходимо и достаточно, чтобы// $$ \Lambda^{(p-1)/p_j} \not\equiv 1 \pmod{p} \quad npu \quad \forall j\in \{1,\dots, \mathfrak r\} \ . $$ **Доказательство.** Необходимость следует из определения первообразного корня. Достаточность. Предположим, что условия теоремы выполнены, но, тем не менее, существует число $ k\in \{1,2,\dots,p-2 \} $ такое, что $ \Lambda^k \equiv 1 \pmod{p} $. Тогда, по теореме 3, число $ p-1 $ должно делиться на $ k_{} $; тогда приведенная ☞ ((:numtheory#каноническое_разложение_числа ЗДЕСЬ)) теорема 4 гарантирует, что хотя бы одно из чисел $ (p-1)/p_j $ делится на $ k_{} $: $ (p-1)/p_j=kq $. Имеем $$ \Lambda^{(p-1)/p_j}=\left(\Lambda^{k} \right)^q \equiv 1 \pmod{p} \ , $$ что противоречит условиям теоремы. Итак, $ \Lambda^k \not\equiv 1 \pmod{p} $ ни для какого показателя $ k_{} $, меньшего $ p-1 $, и, значит, число $ \Lambda $ является первообразным корнем по модулю $ p_{} $. ♦ !!П!! **Пример.** Является ли число: **а)** $ \Lambda=2 $, **б)** $ \Lambda=6 $, первообразным корнем по модулю $ 41 $ ? **Решение.** Имеем $ 41-1=40=2^3\cdot 5 $. Проверяем условия теоремы. Для $ \Lambda=2 $ одно из них не выполнено: $$2^{20}=1024^2\equiv_{_{41}} 40^2 \equiv_{_{41}} (-1)^2 = 1 \ .$$ Для $ \Lambda=6 $: $$6^{20}=2^{20}\cdot 3^{20} \equiv_{_{41}} 3^{20} =\left(3^4 \right)^5 \equiv_{_{41}} (-1)^5=-1 \ , \ 6^8 \equiv_{_{41}} 10 \ , $$ т.е. оба условия выполняются. **Ответ.** **а)** нет, **б)** да. !!Т!! **Теорема 6.** //Для того чтобы число// $ A_{} $ //одновременно удовлетворяло сравнениям// $$ A^{q_1} \equiv 1 \pmod{p}, \dots , A^{q_k} \equiv 1 \pmod{p} \ , $$ //необходимо и достаточно, чтобы оно удовлетворяло сравнению// $$A^{\operatorname{HOD}(q_1,\dots,q_k)} \equiv 1 \pmod{p} \ .$$ **Доказательство.** Достаточность очевидна: $$A^{n} \equiv 1 \pmod{p} \ \Rightarrow \ A^{nt} \equiv 1 \pmod{p} \quad npu \quad \forall t \in \mathbb N \ .$$ Необходимоcть. Если число $ A_{} $ удовлетворяет сравнению $ A^{q} \equiv 1 \pmod{p} $, то, по теореме 3, число $ q_{} $ делится на $ \operatorname{ord}(A) $. Если $ A_{} $ удовлетворяет сравнениям из теоремы, то $ \operatorname{ord}(A) $ будет делителем всех $ q_1,\dots,q_k $, и, следовательно, делителем $ \operatorname{HOD}(q_1,\dots,q_k) $. ♦ !!Т!! **Теорема 7 [Гаусс].** //По любому простому модулю// $ p>2 $ //существует ровно// $ \phi(p-1) $ //первообразных корней во множестве// $ \{1,\dots,p-1\} $. **Доказательство.** Если каноническое разложение числа $ p-1 $ задается формулой $$ p-1=p_1^{{\mathfrak m}_1}p_2^{{\mathfrak m}_2}\times \dots \times p_{\mathfrak r}^{{\mathfrak m}_{\mathfrak r}} \ , $$ то по теореме 5 первообразными корнями по модулю $ p_{} $ среди чисел множества $ \{1,\dots,p-1\} $ будут те и только те, что не удовлетворяют ни одному из сравнений $$ A^{(p-1)/p_1} \equiv 1 \pmod{p} \, , \dots , \ A^{(p-1)/p_{\mathfrak r}} \equiv 1 \pmod{p} \ . $$ Обозначим через: * $ N_j $ --- количество чисел множества $ \{1,\dots,p-1\} $, удовлетворяющих $ j_{} $-му сравнению; * $ N_{j_1j_2} $ --- количество чисел множества $ \{1,\dots,p-1\} $, удовлетворяющих одновременно $ j_1 $-му и $ j_2 $-му сравнениям; * и т.д.; * $ N_{1,2,\dots,\mathfrak r} $ --- количество чисел множества $ \{1,\dots,p-1\} $, удовлетворяющих одновременно всем сравнениям. На основании теорем 4 и 6 имеем $$ N_j=\frac{p-1}{p_j},\ N_{j_1j_2}=\operatorname{HOD} \left( \frac{p-1}{p_{j_1}} \, , \, \frac{p-1}{p_{j_2}} \right) =\frac{p-1}{p_{j_1}p_{j_2}} \ , \, \dots , $$ $$ N_{1,2,\dots,{\mathfrak r}}= \frac{p-1}{p_1p_2\times \dots \times p_{\mathfrak r}} \ . $$ Тогда теорема ((:numtheory#функция_эйлера включений-исключений)) утверждает, что количество чисел множества $ \{1,\dots,p-1\} $, не удовлетворяющих ни одному из сравнений, равно $$ (p-1) - \sum_{1\le j\le{\mathfrak r}} \frac{p-1}{p_j} +\sum_{1\le j_1 < j_2 \le {\mathfrak r}} \frac{p-1}{p_{j_1}p_{j_2}} - \dots + $$ $$ +(-1)^{\mathfrak r} \frac{p-1}{p_1p_2\times \dots \times p_{\mathfrak r}} = $$ $$ =(p-1)\left(1-\frac{1}{p_1} \right)\left(1-\frac{1}{p_2} \right) \times \dots \times \left(1-\frac{1}{p_{\mathfrak r}} \right) \ = \ \phi(p-1) \ . $$ ♦ Примеры показывают, что для простых модулей относительная плотность первообразных корней достаточно велика: $$ \begin{array}{|c|c|c|} \hline p & \phi(p-1)/(p-1) \approx & \Lambda_{\min} \\ \hline 9275976597265732276527865457 & 0.41 & 3 \\ \hline 573549798028708743039820820873497 & 0.32 & 5 \\ \hline 634626763287685763453724586384584746438653493 & 0.48 & 2 \\ \hline 19366902134839432153298400937646552542165422356457691 & 0.26 & 2 \\ \hline \end{array} $$ в третьем столбце приведены значения минимальных первообразных корней. Теперь вернемся к общему случаю составного модуля $ M_{} $ и выясним, почему при некоторых его значениях не существует первообразных корней. Объяснение кроется в том, что в теореме Эйлера значение ((:numtheory#функция_эйлера функции Эйлера)) $ \phi(M) $ часто можно заменить на меньшее --- именно, на значение ((:modular#теорема_эйлера обобщенной функции Эйлера)) $ L(M) $. Как правило $ \phi(M) > L(M) $, так что значение $ L(M) $ дает более точную оценку длины цикла последовательности остатков $ \{ A^j \pmod{M} \}_{j=0}^{\infty} $. Тем не менее, первообразный корень может существовать и для некоторых классов составных модулей. !!Т!! **Теорема 8.** //Первообразные корни по модулю// $ M_{} $ //существуют тогда и только тогда, когда:// 1. либо $ M=p^{n} $ //при// $ p>2 $ //простом и// $ n \in \mathbb N $; 2. либо $ M=2p^n $ //при// $ p>2 $ //простом и// $ n \in \mathbb N $; 3. либо $ M\in \{1,2,4\} $. !!П!! **Пример.** Для $ M=27 $ имеем $ \phi(M) =L(M)=18 $ и числа $ 2,5,11,14,20,23 $ являются первообразными. Если обозначить любое из них через $ \Lambda $, то последовательность $ \{ \Lambda^j \pmod{M} \}_{j=0}^{17} $ пробегает все числа множества $ \{1,2,\dots,26\} $ некратные $ 3_{} $. ====Критерий простоты числа== !!Т!! **Теорема.** //Пусть// $ p>2 $ // и ((:numtheory#каноническое_разложение_числа каноническое разложение)) числа// $ p-1 $ //имеет вид//: $$ p-1=p_1^{{\mathfrak m}_{_1}}p_2^{{\mathfrak m}_{_2}}\times \dots \times p_{\mathfrak r}^{{\mathfrak m}_{_{\mathfrak r}}} \ . $$ //Для того чтобы число// $ p_{} $ //являлось простым, необходимо и достаточно, чтобы существовало число// $ A_{} \in \mathbb Z $ //такое, что для него выполнялись условия//: $$ A^{p-1} \equiv 1 \pmod{p} \quad u \quad A^{(p-1)/p_j} \not\equiv 1 \pmod{p} \quad npu \ \forall j\in \{1,\dots, \mathfrak r\} \ . $$ **Доказательство.** Необходимость. Если $ p_{} $ --- простое, то в качестве $ A_{} $ можно взять любой первообразный корень по модулю $ p_{} $. Достаточность. Если условия теоремы выполняются для некоторого $ A_{} $, то по модулю $ p_{} $ будет: $ \operatorname{ord}(A)=p-1 $, на основании определения порядка и теоремы 3 из предыдущего пункта. По той же теореме число $ \phi(p) $ должно делиться на $ p-1 $. Однако последнее возможно только при условии $ \phi(p)=p-1 $, что и означает простоту $ p_{} $. ♦ !!П!! **Пример.** Является ли число $ 9721 $ простым? **Решение.** Попытаемся подобрать число $ A_{} $, которое удовлетворило бы условиям теоремы. Имеем $ 9721-1=2^3\cdot 3^5 \cdot 5 $ и с помощью ((:modular#вычисление_остатков_степенных_выражений алгоритма "квадрирования-умножения")) вычислим $$A=2 \ \Rightarrow \ 2^{9720} \equiv 1 \pmod{9721} \ , \ 2^{4860} \equiv 1 \pmod{9721} \ . $$ Число $ A=2 $ условию теоремы не удовлетворяет. $$A=3 \ \Rightarrow \ 3^{9720} \equiv 1 \pmod{9721} \ , \ 3^{4860} \equiv 1 \pmod{9721} \ . $$ Число $ A=3 $ условию теоремы не удовлетворяет. $$ A=7 \ \Rightarrow \ 7^{9720} \equiv 1 \pmod{9721} \ , \ 7^{4860} \equiv 9720 \pmod{9721} \ , 7^{3240} \equiv 7796 \pmod{9721} \ , $$ $$ 7^{1944} \equiv 4264 \pmod{9721} \ . $$ Число $ A=7 $ удовлетворяет условию теоремы. **Ответ.** Да. ====Длина периода десятичной дроби== **Задача.** Обратим обыкновенную дробь $ \displaystyle \frac{1}{p} $ в десятичную, получим бесконечную десятичную дробь. Как связана длина периода этой дроби с числом $ p_{} $? !!Т!! **Теорема.** //Длина периода десятичной дроби для// $ \displaystyle \frac{1}{p} $ //является делителем числа// $ p-1 $. **Доказательство.** По ((:modular#теорема_ферма теореме Ферма)) при $ p \not\in \{2,5\} $ число $ 10^{p-1}-1 $ делится на $ p_{} $; таким образом $ 10^{p-1}=Qp+1 $ при $ Q \in \mathbb Z $. Следовательно $$ \frac{10^{p-1}}{p}=Q+\frac{1}{p} \ , $$ и числа $ 1/p $ и $ 10^{p-1}/p $ имеют одинаковые дробные части. Но это и означает, что если в записи периодической дроби для $ 1/p $ переместить точку на $ p-1 $ позицию вправо, то дробная часть сохранит свой вид. Для $ p \in \{2,5\} $ справедливость утверждения теоремы проверяется непосредственной проверкой. ♦ !!П!! **Пример.** $$ \frac{1}{3}=0.(3); \ \frac{1}{7}=0.(142857); \ \frac{1}{11}=0.(09) \ . $$ !!=>!! Длина периода десятичной дроби для $ \displaystyle \frac{1}{p} $ при $ p \not\in \{2,5\} $ равна порядку числа $ 10_{} $ по модулю $ p_{} $, т.е. $ \operatorname{ord}(10) $. !!П!! **Пример.** $$ \frac{1}{103}= 0.\underbrace{0097087378640776699029126213592233}_{34}00970874\dots \ , $$ и действительно, по модулю $ 103 $ имеем $ \operatorname{ord}(10)=34 $. А вот если период $ 0097087378640776699029126213592233 $ разбить на два числа с одинаковым количеством разрядов: $$ 00970873786407766 \quad \mbox{ и } \quad 99029126213592233 $$ и просуммировать, то получим $ 99999999999999999 $, см. ☞ ((https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9C%D0%B8%D0%B4%D0%B8 теорему Миди)). ===Индекс== Итак, для любого первообразного корня $ \Lambda $ последовательность остатков от деления его степеней на $ p_{} $ $$ \Lambda^0=1,\ \Lambda^1 \pmod{p},\dots , \Lambda^{p-2} \pmod{p} $$ представляет переставленные числа $ 1,2,\dots,p-1 $. Для первообразного корня $ \Lambda $ и произвольного целого числа $ A\in \{1,2,\dots,p-1\} $, число, обозначаемое $ \operatorname{ind}_{_{\Lambda}} A $, называется **индексом** $ A_{} $ **по модулю** $ p_{} $ **и основанию** $ \Lambda $, если $$\Lambda^{\operatorname{ind}_{_{\Lambda}} A} \equiv A \pmod{p} \ .$$ Определение индекса очень напоминает определение логарифма положительного вещественного числа $ A_{} $ по основанию положительного вещественного числа $ \Lambda $; в дальнейшем, исследуя свойства $ \operatorname{ind}_{_{\Lambda}} A $, мы установим их параллель со свойствами $ \log_{_{\Lambda}} A $. Эта аналогия привела к тому, что в последние десятилетия в литературе вместо слова "индекс" часто используется выражение "дискретный логарифм"; единственное отличие у этих терминов заключается в том, что индекс определяется не однозначно, а как класс вычетов по модулю $ p-1 $, в то время как значение дискретного логарифма принимается равным единственному представителю этого класса во множестве $ \{0,1,\dots,p-2\} $. Иногда в дальнейшем мы и $ \operatorname{ind}_{_{\Lambda}} A $ будем отождествлять с этим представителем. !!П!! **Пример.** Для $ p=17 $ число $ \Lambda=3 $ является первообразным корнем (см. решение примера ☞ ((#первообразный_корень ЗДЕСЬ)) ). Имеем: $$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline A&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16 \\ \hline \operatorname{ind}_{3} A&0&14&1&12&5&15&11&10&2&3&7&13&4&9&6&8 \\ \hline \end{array} $$ Подобные таблицы можно построить и для других модулей или оснований --- вычислением последовательности $ \{ \Lambda^j \}_{j=0}^{p-2} $ и последующей сортировкой. В общем же случае --- для произвольных модулей или оснований --- задача вычисления индекса или задача **дискретного логарифмирования** является крайне сложной, и, в настоящее время не имеет универсального алгоритма решения. Если же величины индексов по основанию некоторого первообразного корня $ \Lambda $ известны, то это позволяет упростить анализ некоторых задач. Все применения индекса основаны на следующем очевидном факте: при $ \operatorname{HOD} (B,M)=1 $ сравнение $$ A\equiv B \pmod{M} $$ имеет место тогда и только тогда, когда $$\operatorname{ind}_{_{\Lambda}} A \equiv \operatorname{ind}_{_{\Lambda}} B \pmod{\phi(M)} \ . $$ !!Т!! **Теорема.** //Если// $ \Lambda $ --- //первообразный корень по модулю// $ M_{} $ //и// $$ \operatorname{HOD} (A,M)=1,\ \operatorname{HOD} (B,M)=1 \, , $$ //то// $$ \operatorname{ind}_{_{\Lambda}} (A\cdot B) \equiv \operatorname{ind}_{_{\Lambda}} A + \operatorname{ind}_{_{\Lambda}} B \pmod{\phi(M)} \ .$$ **Доказательство.** $$\Lambda^{\operatorname{ind}_{_{\Lambda}} (A\cdot B)} \equiv_{_M} A\cdot B \equiv_{_M} \Lambda^{\operatorname{ind}_{_{\Lambda}} A} \cdot \Lambda^{\operatorname{ind}_{_{\Lambda}} B} = \Lambda^{\operatorname{ind}_{_{\Lambda}} A + \operatorname{ind}_{_{\Lambda}} B} \ . $$ Поскольку $ \Lambda $ является первообразным корнем по модулю $ M_{} $, то $ \operatorname{ord}(\Lambda)=\phi(M) $, и, следовательно, условие $$\Lambda^{\operatorname{ind}_{_{\Lambda}} (A\cdot B)} \equiv \Lambda^{\operatorname{ind}_{_{\Lambda}} A + \operatorname{ind}_{_{\Lambda}} B} \pmod{M} $$ влечет за собой $$\operatorname{ind}_{_{\Lambda}} (A\cdot B)=\operatorname{ind}_{_{\Lambda}} A + \operatorname{ind}_{_{\Lambda}} B \pmod{\phi(M)} \ . $$ ♦ !!=>!! Если $ \Lambda $ --- первообразный корень по модулю $ M_{} $ и $$ \operatorname{HOD} (A_1,M)=1,\dots, \operatorname{HOD} (A_K,M)=1 \, , $$ то $$ \operatorname{ind}_{_{\Lambda}} (A_1 \times \dots \times A_K) \equiv \operatorname{ind}_{_{\Lambda}} A_1 + \dots + \operatorname{ind}_{_{\Lambda}} A_K \pmod{\phi(M)} \ . $$ В частности, при $ \operatorname{HOD} (A,M)=1 $ имеем: $$ \operatorname{ind}_{_{\Lambda}} A^K \equiv K \cdot \operatorname{ind}_{_{\Lambda}} A \pmod{\phi(M)} \ . $$ ==Источники== [1]. **Бухштаб А.А.** //Теория чисел.// М. Просвещение. 1966 [2]. **Uspensky J.V., Heaslet M.A.** //Elementary Number Theory.// New York. McGraw-Hill. 1941