Difference between revisions of "Index"
(Importing text file) |
Ulf Rehmann (talk | contribs) m (tex encoded by computer) |
||
Line 1: | Line 1: | ||
− | + | <!-- | |
+ | 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: | 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 | + | where $ a / b $ |
+ | denotes the root of the equation | ||
− | + | $$ | |
+ | b x \equiv a ( \mathop{\rm mod} m ) . | ||
+ | $$ | ||
− | If | + | 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 | + | 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 | + | 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 | + | 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 | + | 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==== | ====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> | <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==== | ====Comments==== | ||
− | |||
====References==== | ====References==== | ||
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> H. Davenport, "Multiplicative number theory" , Springer (1980)</TD></TR></table> | <table><TR><TD valign="top">[a1]</TD> <TD valign="top"> H. Davenport, "Multiplicative number theory" , Springer (1980)</TD></TR></table> |
Revision as of 22:12, 5 June 2020
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) |
Comments
References
[a1] | H. Davenport, "Multiplicative number theory" , Springer (1980) |
Index. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Index&oldid=47331