|
|
|
|
|
Multiplicative OrderIn number theory, given an integer a and a positive integer n with gcd(a,n) = 1, the multiplicative order of a modulo n is the smallest positive integer k with - ak ≡ 1 (modulo n).
The order of a modulo n is usually written ordn a, or On(a). For example, to determine the multiplicative order of 4 modulo 7, we compute 42 = 16 ≡ 2 (modulo 7) and 43 ≡ 4×2 = 8 ≡ 1 (modulo 7), so ord7(4) = 3. This notion is a special case of the order of group elements: if (G, *) is a group written with the usual multiplicative notation (so that at represents the t-fold product under *), the order of the element a of G is the least positive integer k such that ak=e (where e denotes the identity element of G). The multiplicative order of a number a modulo n is then nothing but the order of a in the group U(n), whose elements are the residues modulo n of the numbers coprime to n, and whose group operation is multiplication modulo n. This is the group of units of the ring Zn; it has φ(n) elements, φ being Euler's totient function. For general reasons then, as a case of Lagrange's theorem, ordna always divides φ(n). If ordn a is actually equal to φ(n) and therefore as large as possible, then a is called a primitive root modulo n. This means that the group U(n) is cyclic and the residue class of a generates it. Not every number n has a primitive root modulo n, but prime numbers always do. If a number n admits a primitive root modulo n, then there are φ(φ(n)) different residue classes modulo n which serve as primitive roots. This is an instance of a general statement about the number of generators of cyclic groups. See also: Modular arithmetic, order (group theory)
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|