Difference between revisions of "Index"
Ulf Rehmann (talk | contribs) m (tex encoded by computer) |
|||
(One intermediate revision by the same user not shown) | |||
Line 45: | Line 45: | ||
form a residue class modulo $ \phi ( m) $. | form a residue class modulo $ \phi ( m) $. | ||
− | The notion of an index is analogous to that of a [[ | + | 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: |
$$ | $$ | ||
Line 146: | Line 146: | ||
====References==== | ====References==== | ||
− | <table><TR><TD valign="top">[1]</TD> <TD valign="top"> I.M. Vinogradov, | + | <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> | |
− | + | <TR><TD valign="top">[a1]</TD> <TD valign="top"> H. Davenport, "Multiplicative number theory" , Springer (1980)</TD></TR> | |
− | + | </table> | |
− | |||
− |
Latest revision as of 17:55, 17 May 2024
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) |
[a1] | H. Davenport, "Multiplicative number theory" , Springer (1980) |
Index. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Index&oldid=47331