# Index

of a number $a$ modulo $m$

The exponent $\gamma$ in the congruence $a \equiv g ^ {\gamma\ (} \mathop{\rm 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 = \mathop{\rm ind} _ {g} a$, or $\gamma = \mathop{\rm ind} a$ for short. Primitive roots exist only for moduli of the form $2 , 4 , p ^ \alpha , 2 p ^ \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 \phi ( m) - 1$, where $\phi ( 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 \leq \gamma \leq \phi ( m) - 1$. Any other index $\gamma ^ \prime$ of $a$ satisfies the congruence $\gamma ^ \prime \equiv \gamma$ $\mathop{\rm mod} \phi ( m)$. Therefore, the indices of $a$ form a residue class modulo $\phi ( 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:

$$\mathop{\rm ind} ( a b ) \equiv \ \mathop{\rm ind} a + \mathop{\rm ind} b \ ( \mathop{\rm mod} \phi ( m) ) ,$$

$$\mathop{\rm ind} ( a ^ {n} ) \equiv n \mathop{\rm ind} a ( \mathop{\rm mod} \phi ( n) ) ,$$

$$\mathop{\rm ind} \frac{a}{b} \equiv \mathop{\rm ind} a - \mathop{\rm ind} b ( \mathop{\rm mod} \phi ( m) ) ,$$

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

$$b x \equiv a ( \mathop{\rm 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} } \ ( \mathop{\rm mod} 2 ^ \alpha ) ,$$

$$a \equiv g _ {1} ^ {\gamma _ {1} } ( \mathop{\rm mod} p _ {1} ^ {\alpha _ {1} } ) ,$$

$${\dots \dots \dots \dots }$$

$$a \equiv g _ {s} ^ {\gamma _ {s} } ( \mathop{\rm 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 \leq \gamma \leq c - 1 ,\ \ 0 \leq \gamma _ {0} \leq c _ {0} - 1 ,$$

$$0 \leq \gamma _ {1} \leq c _ {1} \dots 0 \leq \gamma _ {s} \leq c _ {s} ,$$

where $c _ {i} = \phi ( p _ {i} ^ {\alpha _ {i} } )$, $i = 1 \dots s$, and $c$ and $c _ {0}$ and defined as follows:

$$c = 1 , c _ {0} = 1 \ \ \textrm{ for } \ \alpha = 0 \ \textrm{ or } \alpha = 1 ,$$

$$c = 2 , c _ {0} = 2 ^ {\alpha - 2 } \textrm{ for } \alpha \geq 2 .$$

Every other system $\gamma ^ \prime , \gamma _ {0} ^ \prime \dots \gamma _ {s} ^ \prime$ of indices of $a$ satisfies the congruences

$$\gamma ^ \prime \equiv \gamma ( \mathop{\rm mod} c ) ,\ \gamma _ {0} ^ \prime \equiv \gamma _ {0} ( \mathop{\rm mod} c _ {0} ) \dots \gamma _ {s} ^ \prime \equiv \gamma _ {s} ( \mathop{\rm 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

 [1] I.M. Vinogradov, "Elements of number theory" , Dover, reprint (1954) (Translated from Russian)