Added to Favorites

Related Searches

Nearby Words

In modular arithmetic the set of congruence classes relatively prime to the modulus n form a group under multiplication called the multiplicative group of integers modulo n. It is also called the group of primitive residue classes modulo n. In the theory of rings, a branch of abstract algebra, it is described as the group of units of the ring of integers modulo n. (Units refers to elements with a multiplicative inverse.) ## Group Axioms

## Notation

## Structure

### Powers of 2

### Powers of odd primes

### General composite numbers

## Order

## Exponent

## Generators

## Table

## See also

## Notes

## References

## External links

This group is fundamental in number theory. It has found applications in cryptography, integer factorization, and primality testing. For example, by finding the order (ie. the size) of the group, one can determine if n is prime: n is prime if and only if the order is n – 1.

It is easy to establish that under multiplication the congruence classes (mod n) which are relatively prime to n satisfy the axioms for an Abelian group.

Closure: if a and b are both relatively prime to n, so is ab.

Inverse: Finding x satisfying ax ≡ 1 (mod n) is the same as solving ax + ny = 1, which can be done by Euclid's algorithm.

Identity: 1 is the identity.

Associativity and commutivity: These follow from the corresponding facts for the integers, plus the fact that the map that takes an integer to its congruence class (mod n) is a ring homomorphism.

The ring of integers (mod n) is denoted $mathbb\{Z\}/nmathbb\{Z\}$ or $mathbb\{Z\}/(n)$ (ie. the ring of integers modulo the ideal nZ = (n) consisting of the multiples of n) or by $mathbb\{Z\}\_n.$ Depending on the author its group of units may be written $(mathbb\{Z\}/nmathbb\{Z\})^*,$ $(mathbb\{Z\}/nmathbb\{Z\})^times,$ $U(mathbb\{Z\}/nmathbb\{Z\}),$ or similar notations. This article uses $(mathbb\{Z\}/nmathbb\{Z\})^times.$

Modulo 2 there is only one relatively prime congruence class, 1, so $(mathbb\{Z\}/2mathbb\{Z\})^times\; cong\; \{1\}$ is trivial.

Modulo 4 there are two relatively prime congruence classes, 1 and 3, so $(mathbb\{Z\}/4mathbb\{Z\})^times\; cong\; C\_2,$ the cyclic group with two elements.

Modulo 8 there are four relatively prime classes, 1, 3, 5 and 7. The square of each of these is 1, so $(mathbb\{Z\}/8mathbb\{Z\})^times\; cong\; C\_2\; times\; C\_2,$ the Klein four-group.

Modulo 16 there are eight relatively prime classes 1, 3, 5, 7, 9, 11, 13 and 15. $\{pm\; 1,\; pm\; 7\}cong\; C\_2\; times\; C\_2,$ is the 2-torsion subgroup (ie. the square of each element is 1), so $(mathbb\{Z\}/16mathbb\{Z\})^times$ is not cyclic. The powers of 3, $\{1,\; 3,\; 9,\; 11\}$ are a subgroup of order 4, as are the powers of 5, $\{1,\; 5,\; 9,\; 13\}.;;$ Thus $(mathbb\{Z\}/16mathbb\{Z\})^times\; cong\; C\_2\; times\; C\_4.$

The pattern shown by 8 and 16 holds for higher powers 2^{k}, k > 2: $\{pm\; 1,\; 2^\{\; k-1\}\; pm\; 1\}cong\; C\_2\; times\; C\_2,$ is the 2-torsion subgroup (so $(mathbb\{Z\}/2^kmathbb\{Z\})^times$ is not cyclic) and the powers of 3 are a subgroup of order 2^{k – 2}, so $(mathbb\{Z\}/2^kmathbb\{Z\})^times\; cong\; C\_2\; times\; C\_\{2^\{k-2\}\}.$

For powers of odd primes p^{k} the group is cyclic: $;;(mathbb\{Z\}/p^kmathbb\{Z\})^times\; cong\; C\_\{p^\{k-1\}(p-1)\}\; cong\; C\_\{varphi(p^k)\}.$

The Chinese remainder theorem says that if $;;n=p\_1^\{k\_1\}p\_2^\{k\_2\}p\_3^\{k\_3\}dots,\; ;$ then the ring $mathbb\{Z\}/nmathbb\{Z\}$ is the direct product of the rings corresponding to each of its prime power factors:

- $mathbb\{Z\}/nmathbb\{Z\}\; cong\; mathbb\{Z\}/\{p\_1^\{k\_1\}\}mathbb\{Z\};\; times\; ;mathbb\{Z\}/\{p\_2^\{k\_2\}\}mathbb\{Z\}\; ;times;\; mathbb\{Z\}/\{p\_3^\{k\_3\}\}mathbb\{Z\}dots;;$

Similarly, the group of units $(mathbb\{Z\}/nmathbb\{Z\})^times$ is the direct product of the groups corresponding to each of the prime power factors:

- $(mathbb\{Z\}/nmathbb\{Z\})^timescong\; (mathbb\{Z\}/\{p\_1^\{k\_1\}\}mathbb\{Z\})^times\; times\; (mathbb\{Z\}/\{p\_2^\{k\_2\}\}mathbb\{Z\})^times\; times\; (mathbb\{Z\}/\{p\_3^\{k\_3\}\}mathbb\{Z\})^times\; dots;.$

The order of the group is given by Euler's totient function: $|\; (mathbb\{Z\}/nmathbb\{Z\})^times|=varphi(n).$ This is the product of the orders of the cyclic groups in the direct product.

The exponent is given by the Carmichael function $lambda(n),$ the least common multiple of the orders of the cyclic groups. This means that if a and n are relatively prime, $a^\{lambda(n)\}\; equiv\; 1\; pmod\; n.$

$(mathbb\{Z\}/nmathbb\{Z\})^times$ is cyclic if and only if $varphi(n)=lambda(n).$ This is the case for n a power of an odd prime, twice a power of an odd prime, 2, or 4. In this case a generator is called a primitive root modulo n.

Since all the $(mathbb\{Z\}/nmathbb\{Z\})^times,$ n = 1, 2, ..., 7 are cyclic, another way to state this is: If n < 8 then $;(mathbb\{Z\}/nmathbb\{Z\})^times$ has a primitive root. If n ≥ 8 $;(mathbb\{Z\}/nmathbb\{Z\})^times$ has a primitive root unless n is divisible by 4 or by two distinct odd primes.

In the general case there is one generator for each cyclic direct factor.

This table shows the structure and generators of $(mathbb\{Z\}/nmathbb\{Z\})^times$ for small values of n. The generators are not unique (mod n); e.g. (mod 16) both {–1, 3} and {–1, 5} will work. The generators are listed in the same order as the direct factors.

For example take n = 20. $varphi(20)=8$ means that the order of $(mathbb\{Z\}/20mathbb\{Z\})^times$ is 8 (i.e. there are 8 numbers less than 20 and coprime to it); $lambda(20)=4$ that the fourth power of any number relatively prime to 20 is ≡ 1 (mod 20); and as for the generators, 19 has order 2, 3 has order 4, and every member of $(mathbb\{Z\}/20mathbb\{Z\})^times$ is of the form 19^{a} × 3^{b}, where a is 0 or 1 and b is 0, 1, 2, or 3.

The powers of 19 are {±1} and the powers of 3 are {3, 9, 7, 1}. The latter and their negatives (mod 20), {17, 11, 13, 19} are all the numbers less than 20 and prime to it. The fact that the order of 19 is 2 and the order of 3 is 4 implies that the fourth power of every member of $mathbb\{Z\}\_\{20\}^times$ is ≡ 1 (mod 20).

$n$ | $(mathbb\{Z\}/nmathbb\{Z\})^times$ | $varphi(n)$ | $lambda(n)$ | generators | $n$ | $(mathbb\{Z\}/nmathbb\{Z\})^times$ | $varphi(n)$ | $lambda(n)$ | generators | |
---|---|---|---|---|---|---|---|---|---|---|

2 | {1} | 1 | 1 | 1 | 33 | C_{2}×C_{10}
| 20 | 10 | 10, 2 | |

3 | C_{2}
| 2 | 2 | 2 | 34 | C_{16}
| 16 | 16 | 3 | |

4 | C_{2}
| 2 | 2 | 3 | 35 | C_{2}×C_{12}
| 24 | 12 | 6, 2 | |

5 | C_{4}
| 4 | 4 | 2 | 36 | C_{2}×C_{6}
| 12 | 6 | 19, 5 | |

6 | C_{2}
| 2 | 2 | 5 | 37 | C_{36}
| 36 | 36 | 2 | |

7 | C_{6}
| 6 | 6 | 3 | 38 | C_{18}
| 18 | 18 | 3 | |

8 | C_{2}×C_{2}
| 4 | 2 | 7, 3 | 39 | C_{2}×C_{12}
| 24 | 12 | 38, 2 | |

9 | C_{6}
| 6 | 6 | 2 | 40 | C_{2}×C_{2}×C_{4}
| 16 | 4 | 39, 11, 3 | |

10 | C_{4}
| 4 | 4 | 3 | 41 | C_{40}
| 40 | 40 | 6 | |

11 | C_{10}
| 10 | 10 | 2 | 42 | C_{2}×C_{6}
| 12 | 6 | 13, 5 | |

12 | C_{2}×C_{2}
| 4 | 2 | 5, 7 | 43 | C_{42}
| 42 | 42 | 3 | |

13 | C_{12}
| 12 | 12 | 2 | 44 | C_{2}×C_{10}
| 20 | 10 | 43, 3 | |

14 | C_{6}
| 6 | 6 | 3 | 45 | C_{2}×C_{12}
| 24 | 12 | 44, 2 | |

15 | C_{2}×C_{4}
| 8 | 4 | 14, 2 | 46 | C_{22}
| 22 | 22 | 5 | |

16 | C_{2}×C_{4}
| 8 | 4 | 15, 3 | 47 | C_{46}
| 46 | 46 | 5 | |

17 | C_{16}
| 16 | 16 | 3 | 48 | C_{2}×C_{2}×C_{4}
| 16 | 4 | 47, 7, 5 | |

18 | C_{6}
| 6 | 6 | 5 | 49 | C_{42}
| 42 | 42 | 3 | |

19 | C_{18}
| 18 | 18 | 2 | 50 | C_{20}
| 20 | 20 | 3 | |

20 | C_{2}×C_{4}
| 8 | 4 | 19, 3 | 51 | C_{2}×C_{16}
| 32 | 16 | 50, 5 | |

21 | C_{2}×C_{6}
| 12 | 6 | 20, 2 | 52 | C_{2}×C_{12}
| 24 | 12 | 51, 7 | |

22 | C_{10}
| 10 | 10 | 7 | 53 | C_{52}
| 52 | 52 | 2 | |

23 | C_{22}
| 22 | 22 | 5 | 54 | C_{18}
| 18 | 18 | 5 | |

24 | C_{2}×C_{2}×C_{2}
| 8 | 2 | 5, 7, 13 | 55 | C_{2}×C_{20}
| 40 | 20 | 21, 2 | |

25 | C_{20}
| 20 | 20 | 2 | 56 | C_{2}×C_{2}×C_{6}
| 24 | 6 | 13, 29, 3 | |

26 | C_{12}
| 12 | 12 | 7 | 57 | C_{2}×C_{18}
| 36 | 18 | 20, 2 | |

27 | C_{18}
| 18 | 18 | 2 | 58 | C_{28}
| 28 | 28 | 3 | |

28 | C_{2}×C_{6}
| 12 | 6 | 13, 3 | 59 | C_{58}
| 58 | 58 | 2 | |

29 | C_{28}
| 28 | 28 | 2 | 60 | C_{2}×C_{2}×C_{4}
| 16 | 4 | 11, 19, 7 | |

30 | C_{2}×C_{4}
| 8 | 4 | 11, 7 | 61 | C_{60}
| 60 | 60 | 2 | |

31 | C_{30}
| 30 | 30 | 3 | 62 | C_{30}
| 30 | 30 | 3 | |

32 | C_{2}×C_{8}
| 16 | 8 | 31, 3 | 63 | C_{6}×C_{6}
| 36 | 6 | 2, 5 |

Lenstra elliptic curve factorization

The Disquisitiones Arithmeticae has been translated from Gauss's Ciceronian Latin into English and German. The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes.

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Monday September 22, 2008 at 21:19:26 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Monday September 22, 2008 at 21:19:26 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Search another word or see **Multiplicative group of integers modulo n**on
Dictionary |
Thesaurus
|Spanish

Copyright © 2014 Dictionary.com, LLC. All rights reserved.