Namespaces
Variants
Actions

Difference between revisions of "Index"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
''of a number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i0506402.png" /> modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i0506403.png" />''
+
<!--
 +
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.
 +
-->
  
The exponent <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i0506404.png" /> in the [[Congruence|congruence]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i0506405.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i0506406.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i0506407.png" /> are relatively prime integers and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i0506408.png" /> is a fixed [[Primitive root|primitive root]] modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i0506409.png" />. The index of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064010.png" /> modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064011.png" /> is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064012.png" />, or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064013.png" /> for short. Primitive roots exist only for moduli of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064014.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064015.png" /> is a prime number; consequently, the notion of an index is only defined for these moduli.
+
{{TEX|auto}}
 +
{{TEX|done}}
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064016.png" /> is a primitive root modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064017.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064018.png" /> runs through the values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064019.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064020.png" /> is the [[Euler function|Euler function]], then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064021.png" /> runs through a [[Reduced system of residues|reduced system of residues]] modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064022.png" />. Consequently, for each number relatively prime with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064023.png" /> there exist a unique index <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064024.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064025.png" />. Any other index <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064026.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064027.png" /> satisfies the congruence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064028.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064029.png" />. Therefore, the indices of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064030.png" /> form a residue class modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064031.png" />.
+
''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:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064032.png" /></td> </tr></table>
+
$$
 +
\mathop{\rm ind}  ( a b )  \equiv \
 +
\mathop{\rm ind}  a +  \mathop{\rm ind}  b \
 +
(  \mathop{\rm mod}  \phi ( m) ) ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064033.png" /></td> </tr></table>
+
$$
 +
\mathop{\rm ind}  ( a  ^ {n} )  \equiv  n  \mathop{\rm ind}  a  (  \mathop{\rm mod}  \phi ( n) ) ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064034.png" /></td> </tr></table>
+
$$
 +
\mathop{\rm ind} 
 +
\frac{a}{b}
 +
  \equiv  \mathop{\rm ind}  a - \mathop{\rm ind}  b  (  \mathop{\rm mod}  \phi ( m) ) ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064035.png" /> denotes the root of the equation
+
where $  a / b $
 +
denotes the root of the equation
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064036.png" /></td> </tr></table>
+
$$
 +
b x  \equiv  a  (  \mathop{\rm mod}  m ) .
 +
$$
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064037.png" /> is the canonical factorization of an arbitrary natural number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064038.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064039.png" /> are primitive roots modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064040.png" />, respectively, then for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064041.png" /> relatively primitive with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064042.png" /> there exist integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064043.png" /> for which
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064044.png" /></td> </tr></table>
+
$$
 +
a  \equiv  ( - 1 )  ^  \gamma
 +
5 ^ {\gamma _ {0} } \
 +
(  \mathop{\rm mod}  2  ^  \alpha  ) ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064045.png" /></td> </tr></table>
+
$$
 +
a  \equiv  g _ {1} ^ {\gamma _ {1} }  (  \mathop{\rm mod}  p _ {1} ^ {\alpha _ {1} } ) ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064046.png" /></td> </tr></table>
+
$$
 +
{\dots \dots \dots \dots }
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064047.png" /></td> </tr></table>
+
$$
 +
a  \equiv  g _ {s} ^ {\gamma _ {s} }  (  \mathop{\rm mod}  p _ {s} ^ {\alpha _ {s} } ) .
 +
$$
  
The above system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064048.png" /> is called a system of indices of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064050.png" /> modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064051.png" />. To each number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064052.png" /> relatively prime with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064053.png" /> corresponds a unique system of indices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064054.png" /> for which
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064055.png" /></td> </tr></table>
+
$$
 +
0  \leq  \gamma  \leq  c - 1 ,\ \
 +
0  \leq  \gamma _ {0}  \leq  c _ {0} - 1 ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064056.png" /></td> </tr></table>
+
$$
 +
0 \leq  \gamma _ {1}  \leq  c _ {1} \dots 0  \leq  \gamma _ {s}  \leq  c _ {s} ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064057.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064058.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064059.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064060.png" /> and defined as follows:
+
where $  c _ {i} = \phi ( p _ {i} ^ {\alpha _ {i} } ) $,  
 +
$  i = 1 \dots s $,  
 +
and $  c $
 +
and $  c _ {0} $
 +
and defined as follows:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064061.png" /></td> </tr></table>
+
$$
 +
= 1 , c _ {0}  = 1 \ \
 +
\textrm{ for } \
 +
\alpha = 0 \
 +
\textrm{ or }  \alpha = 1 ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064062.png" /></td> </tr></table>
+
$$
 +
= 2 , c _ {0}  = 2 ^ {\alpha - 2 }  \textrm{ for }  \alpha \geq  2 .
 +
$$
  
Every other system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064063.png" /> of indices of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064064.png" /> satisfies the congruences
+
Every other system $  \gamma  ^  \prime  , \gamma _ {0}  ^  \prime  \dots \gamma _ {s}  ^  \prime  $
 +
of indices of $  a $
 +
satisfies the congruences
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064065.png" /></td> </tr></table>
+
$$
 +
\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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064066.png" /> modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064067.png" /> is convenient for the explicit construction of characters of the multiplicative group of reduced residue classes modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050640/i05064068.png" />.
+
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>

Latest 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)
How to Cite This Entry:
Index. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Index&oldid=17202
This article was adapted from an original article by S.A. Stepanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article