Index

of a number $a$ modulo $m$

The exponent $\gamma$ in the congruence $a\equiv g^{\gamma (}\mathrm{mod}m)$, where $a$ and $m$ are relatively prime integers and $g$ is a fixed primitive root modulo $m$. The index of $a$ modulo $m$ is denoted by $\gamma ={\mathrm{ind}}_{g}a$, or $\gamma =\mathrm{ind}a$ for short. Primitive roots exist only for moduli of the form $2,4,p^{\alpha },2p^{\alpha }$, where $p>2$ is a prime number; consequently, the notion of an index is only defined for these moduli.

If $g$ is a primitive root modulo $m$ and $\gamma$ runs through the values $0\dots \varphi (m)-1$, where $\varphi (m)$ is the Euler function, then $g^{\gamma }$ runs through a reduced system of residues modulo $m$. Consequently, for each number relatively prime with $m$ there exist a unique index $\gamma$ for which $0\le \gamma \le \varphi (m)-1$. Any other index ${\gamma }^{\prime }$ of $a$ satisfies the congruence ${\gamma }^{\prime }\equiv \gamma$ $\mathrm{mod}\varphi (m)$. Therefore, the indices of $a$ form a residue class modulo $\varphi (m)$.

The notion of an index is analogous to that of a logarithm of a number, and the index satisfies a number of properties of the logarithm, namely:

$$\mathrm{ind}(ab)\equiv \mathrm{ind}a+\mathrm{ind}b(\mathrm{mod}\varphi (m)),$$

$$\mathrm{ind}(a^n)\equiv n\mathrm{ind}a(\mathrm{mod}\varphi (n)),$$

$$\mathrm{ind}\frac{a}{b}\equiv \mathrm{ind}a-\mathrm{ind}b(\mathrm{mod}\varphi (m)),$$

where $a/b$ denotes the root of the equation

$$bx\equiv a(\mathrm{mod}m).$$

If $m=2^{\alpha }{p}_1^{{\alpha }_1}\dots p_s^{{\alpha }_s}$ is the canonical factorization of an arbitrary natural number $m$ and $g_1\dots g_s$ are primitive roots modulo $p_1^{{\alpha }_1}\dots p_s^{{\alpha }_s}$, respectively, then for each $a$ relatively primitive with $m$ there exist integers $\gamma ,{\gamma }_0\dots {\gamma }_s$ for which

$$a\equiv (-1{)}^{\gamma }{5}^{{\gamma }_0}(\mathrm{mod}{2}^{\alpha }),$$

$$a\equiv g_1^{{\gamma }_1}(\mathrm{mod}{p}_1^{{\alpha }_1}),$$

$$\dots \dots \dots \dots$$

$$a\equiv g_s^{{\gamma }_s}(\mathrm{mod}{p}_s^{{\alpha }_s}).$$

The above system $\gamma ,{\gamma }_0\dots {\gamma }_s$ is called a system of indices of $a$ modulo $m$. To each number $a$ relatively prime with $m$ corresponds a unique system of indices $\gamma ,{\gamma }_0\dots {\gamma }_s$ for which

$$0\le \gamma \le c-1,0\le {\gamma }_0\le c_0-1,$$

$$0\le {\gamma }_1\le c_1\dots 0\le {\gamma }_s\le c_s,$$

where $c_i=\varphi (p_i^{{\alpha }_i})$, $i=1\dots s$, and $c$ and $c_0$ and defined as follows:

$$c=1,c_0=1\text{ for }\alpha =0\text{ or }\alpha =1,$$

$$c=2,c_0=2^{\alpha -2}\text{ for }\alpha \ge 2.$$

Every other system ${\gamma }^{\prime },{\gamma }_0^{\prime }\dots {\gamma }_s^{\prime }$ of indices of $a$ satisfies the congruences

$${\gamma }^{\prime }\equiv \gamma (\mathrm{mod}c),{\gamma }_0^{\prime }\equiv {\gamma }_0(\mathrm{mod}{c}_0)\dots {\gamma }_s^{\prime }\equiv {\gamma }_s(\mathrm{mod}{c}_s).$$

The notion of a system of indices of $a$ modulo $m$ is convenient for the explicit construction of characters of the multiplicative group of reduced residue classes modulo $m$.

References[edit]