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)

References

[a1]	H. Davenport, "Multiplicative number theory" , Springer (1980)