View source for Index

<!--
i0506402.png
$#A+1 = 66 n = 0
$#C+1 = 66 : ~/encyclopedia/old_files/data/I050/I.0500640 Index
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

''of a number  $  a $
modulo  $  m $''

The exponent  $  \gamma $
in the [[Congruence|congruence]]  $  a \equiv g  ^ {\gamma\ (}  \mathop{\rm mod}  m ) $, 
where  $  a $
and  $  m $
are relatively prime integers and  $  g $
is a fixed [[Primitive root|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|Euler function]], then  $  g  ^  \gamma  $
runs through a [[Reduced system of residues|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|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====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  I.M. Vinogradov,   "Elements of number theory" , Dover, reprint  (1954)  (Translated from Russian)</TD></TR></table>

====Comments====

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  H. Davenport,   "Multiplicative number theory" , Springer  (1980)</TD></TR></table>