Инструменты сайта


Для понимания материалов настоящего раздела рекомендуется ознакомиться с разделом МОДУЛЯРНАЯ АРИФМЕТИКА. Сложность материалов раздела — повышенная.

Индекс (дискретный логарифм)

Первообразный корень

Задача. Найти длину цикла последовательности $ \{A^j \pmod{M} \}_{j=0}^{\infty} $ .

Для случая простого модуля верхняя оценка для длины цикла дается теоремой Ферма:

Т

Теорема [Ферма (малая)]. Если $ 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 ЗДЕСЬ ), по крайней мере один из сомножителей справа должен делиться на простое $ 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_{} $ в каноническом разложении этого числа1): $$ \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<r<\operatorname{ord} (A) $. Тогда $$1\equiv_{_M} A^{n} = \left( A^{\operatorname{ord} (A)} \right)^qA^r \equiv_{_M} A^r \ , $$ и, следовательно, число $ \operatorname{ord} (A) $ не является минимальным показателем степени числа $ A_{} $, сравнимой с единицей по модулю $ M_{} $. Мы пришли к противоречию с определением $ \operatorname{ord} (A) $. Второе утверждение теоремы следует из первого и теоремы Эйлера.

=>

Для любого $ 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<n $. Применяем теорему 3.

Итак, решение задачи, поставленной в начале пункта — об оценке длины цикла последовательности $ \{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 раздела РЕШЕНИЕ НЕЛИНЕЙНЫХ СРАВНЕНИЙ следует, что половина из чисел $ \{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 $ называется первообразным корнем2) по модулю $ M_{} $, если $ \operatorname{ord} (\Lambda)=\phi(M) $.

Это определение сходно по смыслу с определением первообразного комплексного корня из единицы. В самом деле, первообразный корень из единицы степени $ 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. Если каноническое разложение числа $ 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_{} $; тогда приведенная ЗДЕСЬ теорема 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}} \ . $$ Тогда теорема включений-исключений утверждает, что количество чисел множества $ \{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_{} $ и выясним, почему при некоторых его значениях не существует первообразных корней. Объяснение кроется в том, что в теореме Эйлера значение функции Эйлера $ \phi(M) $ часто можно заменить на меньшее — именно, на значение обобщенной функции Эйлера $ 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 $ и каноническое разложение числа $ 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 $ и с помощью алгоритма "квадрирования-умножения" вычислим $$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 $.

Доказательство. По теореме Ферма при $ 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 $, см. теорему Миди.

Индекс

Итак, для любого первообразного корня $ \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

1)
parity (англ.) — четность.
2)
В англоязычной литературе принято название primitive root.
modular/index.txt · Последние изменения: 2022/02/15 23:52 — au