Индексы

$\newcommand\ind{\mathop{\rm ind}\nolimits} \ind _ g a\pmod m$ — такое $x$, что $g^ x \equiv a\pmod m$.

К сожалению, если $m \notin \{ 2, 4, p^\alpha , 2p^\alpha \}$, то индексы не определены. Но кое-что можно сделать: рассмотреть систему индексов.

1) Пусть $m = p_1^{\alpha _1}\cdot \ldots \cdot p_ k^{\alpha _ k}$, $p_ i$ — нечётное простое.

Берут первообразные корни по модулям $p_1^{\alpha _1}, \ldots , p_ k^{\alpha _ k}$ — $g_1, \ldots , g_ k$ — и рассматривают соответствующие индексы $\gamma _1, \ldots , \gamma _ k$ — система индексов.

2) Пусть $m = 2^\alpha , \alpha \geqslant 3$.

$5^{2^{\alpha -2}} \equiv 1\ (2^\alpha )$.

$5^{2^{\alpha -3}} = (1 + 4)^{2^{\alpha -3}}$.

$(1 + 4)^2 = 1 + 8 + 16 = 1+8t$, $t$ — нечётное.

$(1 + 4)^{2^2} = 1 + 16t_1$, $t_1$ — нечётное.

…

$(1 + 4)^{2^{\alpha -3}} = 1 + 2^{\alpha -1}t_{\alpha -4}, t_{\alpha -4}$ — нечётное.

Значит, $\tau (5) = 2^{\alpha -2}$. $5^1, 5^2, \ldots , 5^\tau$ — различные mod $2^\alpha$.

$-5^1, -5^2, \ldots , -5^\tau$ — различные mod $2^\alpha$. При этом они не совпадают с первой группой. Действительно $-5^ k \equiv 5^ l\pmod{2^\alpha} \iff -5^ k \equiv 5^ l\pmod 4$, противоречие.

Всего чисел здесь $2^{\alpha -1} = \varphi (2^\alpha ) = \varphi (m) \Rightarrow$ любое нечётное число по mod $2^\alpha$ представляется в виде $(-1)^{\beta _0} 5^{\beta _1}$, где $\beta _0\in \{ 0, 1\} , \beta _1 \in \{ 1, \ldots , 2^{\alpha -1}\}$.

Тогда $(\beta _0, \beta _1)$ можно считать системой индексов по mod $2^\alpha , \alpha \geqslant 3$.

3) Пусть $m = 2^{\alpha _0}p_1^{\alpha _1}\cdot \ldots \cdot p_ k^{\alpha _ k}$.

Системой индексов будет либо $(\gamma _0, \ldots , \gamma _ k)$, если $\alpha _0\leqslant 2$, либо $(\beta _0, \beta _1, \gamma _1, \ldots , \gamma _ k)$, если $\alpha _0\geqslant 3$.