TOPICS
Search

Multiplicative Order


Let n be a positive number having primitive roots. If g is a primitive root of n, then the numbers 1, g, g^2, ..., g^(phi(n)-1) form a reduced residue system modulo n, where phi(n) is the totient function. In this set, there are phi(phi(n)) primitive roots, and these are the numbers g^c, where c is relatively prime to phi(n).

The smallest exponent e for which b^e=1 (mod n), where b and n are given numbers, is called the multiplicative order (or sometimes haupt-exponent or modulo order) of b (mod n).

The multiplicative order is implemented in the Wolfram Language as MultiplicativeOrder[g, n].

The number of bases having multiplicative order e is phi(e), where phi(e) is the totient function. Cunningham (1922) published the multiplicative order for primes to 25409 and bases 2, 3, 5, 6, 7, 10, 11, and 12.

Multiplicative orders exist for n that are relatively prime to b. For example, the multiplicative order of 10 (mod 7) is 6, since

 10^6=1 (mod 7).
(1)

The multiplicative order of 10 mod an integer n relatively prime to 10 gives the period of the decimal expansion of the reciprocal of n (Glaisher 1878, Lehmer 1941). For example, the haupt-exponent of 10 (mod 13) is 6, and

 1/(13)=0.076923^_,
(2)

which has period 6.

The following table gives the first few multiplicative orders for bases b (mod n), where n is the series of numbers relatively prime to b.

bOEIShaupt-exponents
2A0023262, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, ...
3A0509751, 2, 4, 6, 2, 4, 5, 3, 6, 4, 16, 18, 4, 5, ...
4A0509761, 2, 3, 3, 5, 6, 2, 4, 9, 3, 11, 10, 9, 14, ...
5A0509771, 2, 1, 2, 6, 2, 6, 5, 2, 4, 6, 4, 16, 6, 9, ...
6A0509781, 2, 10, 12, 16, 9, 11, 5, 14, ...
7A0509791, 1, 2, 4, 1, 2, 3, 4, 10, 2, 12, 4, 2, 16, ...
8A0509802, 4, 1, 2, 10, 4, 4, 8, 6, 2, 11, 20, 6, 28, ...
9A0509811, 1, 2, 3, 1, 2, 5, 3, 3, 2, 8, 9, 2, 5, 11, ...
10A0023291, 6, 1, 2, 6, 16, 18, 6, 22, 3, 28, ...

If a is an arbitrary integer relatively prime to n, then there exists among the numbers 0, 1, 2, ..., phi(n)-1 exactly one number mu such that

 a=g^mu (mod n).
(3)

The number mu is then called the generalized multiplicative order (or discrete logarithm; Schneier 1996, p. 501) of a with respect to the base g modulo n. Note that Nagell (1951, p. 112) instead uses the term "index" and writes

 mu=ind_ga (mod n).
(4)

For example, the number 7 is the least positive primitive root of n=41, and since 15=7^3 (mod 41), the number 15 has multiplicative order 3 with respect to base 7 (modulo 41) (Nagell 1951, p. 112).

The generalized multiplicative order is implemented in the Wolfram Language as MultiplicativeOrder[g, n, {a1}], or more generally as MultiplicativeOrder[g, n, {a1, a2, ...}].

If the primitive roots g_1=-1 and g_2=1 are chosen, the resulting function is called the suborder function and is denoted sord_n(a). If the single primitive root g_1=1 is chosen, then the function reduces to "the" (i.e., ungeneralized) multiplicative order, denoted ord_n(a), implemented in the Wolfram Language as MultiplicativeOrder[a, n]. This function is sometimes also known as the discrete logarithm (or, more confusingly, as the "index," a term that Nagell applied to the case of general g).


See also

Carmichael Function, Complete Residue System, Congruence, Discrete Logarithm, Full Reptend Prime, Out-Shuffle, Polynomial Order, Primitive Root, Suborder Function

Explore with Wolfram|Alpha

References

Burton, D. M. "The Order of an Integer Modulo n." §8.1 in Elementary Number Theory, 4th ed. Dubuque, IA: William C. Brown Publishers, pp. 184-190, 1989.Cunningham, A. Haupt-Exponents, Residue Indices, Primitive Roots. London: F. Hodgson, 1922.Glaisher, J. W. L. "Periods of Reciprocals of Integers Prime to 10." Proc. Cambridge Philos. Soc. 3, 185-206, 1878.Lehmer, D. H. "Guide to Tables in the Theory of Numbers." Bulletin No. 105. Washington, DC: National Research Council, pp. 7-12, 1941.Nagell, T. "Exponent of an Integer Modulo n" and "The Index Calculus." §31 and 33 in Introduction to Number Theory. New York: Wiley, pp. 102-106 and 111-115, 1951.Odlyzko, A. "Discrete Logarithms: The Past and the Future." http://www.dtc.umn.edu/~odlyzko/doc/discrete.logs.future.pdf.Schneier, B Applied Cryptography: Protocols, Algorithms, and Source Code in C, 2nd ed. New York: Wiley, 1996.Sloane, N. J. A. Sequences A002326/M0936, A002329/M4045, A050975, A050976, A050977, A050978, A050979, A050980, and A050981 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Multiplicative Order

Cite this as:

Weisstein, Eric W. "Multiplicative Order." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/MultiplicativeOrder.html

Subject classifications