From Encyclopedia of Mathematics
Revision as of 17:20, 7 February 2011 by (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

of a number modulo

The exponent in the congruence , where and are relatively prime integers and is a fixed primitive root modulo . The index of modulo is denoted by , or for short. Primitive roots exist only for moduli of the form , where is a prime number; consequently, the notion of an index is only defined for these moduli.

If is a primitive root modulo and runs through the values , where is the Euler function, then runs through a reduced system of residues modulo . Consequently, for each number relatively prime with there exist a unique index for which . Any other index of satisfies the congruence . Therefore, the indices of form a residue class modulo .

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:

where denotes the root of the equation

If is the canonical factorization of an arbitrary natural number and are primitive roots modulo , respectively, then for each relatively primitive with there exist integers for which

The above system is called a system of indices of modulo . To each number relatively prime with corresponds a unique system of indices for which

where , , and and and defined as follows:

Every other system of indices of satisfies the congruences

The notion of a system of indices of modulo is convenient for the explicit construction of characters of the multiplicative group of reduced residue classes modulo .


[1] I.M. Vinogradov, "Elements of number theory" , Dover, reprint (1954) (Translated from Russian)



[a1] H. Davenport, "Multiplicative number theory" , Springer (1980)
How to Cite This Entry:
Index. Encyclopedia of Mathematics. URL:
This article was adapted from an original article by S.A. Stepanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article