# Multiplicative group of integers modulo n

The **multiplicative group of integers modulo n**, written \( (\mathbb{Z}/n\mathbb{Z})^{\times} \) or \( U(n) \), is the group formed by the residue classes modulo \( n \) that are coprime to \( n \), with multiplication modulo \( n \) as the operation. It is a finite abelian group whose order is [Euler's totient function](https://www.edgepedia.org/eulers-totient-function) \( \varphi(n) \), and its structure is completely described by the [Chinese remainder theorem](https://www.edgepedia.org/chinese-remainder-theorem) together with the structure of unit groups of prime-power moduli.<sup>[1](https://calc-path.com/abstract-algebra/modules/groups)</sup><sup> • </sup><sup>[2](https://finitegroupdatabase.com/c/multiplicative)</sup>

| Key fact | Detail |
|---|---|
| Elements | The classes \( [a]_n \) with \( \gcd(a, n) = 1 \); these are exactly the classes with a multiplicative inverse modulo \( n \)<sup>[3](https://www.math.gordon.edu/ntic/ntic2017/section-groups-numbers.html)</sup> |
| Order | \( \varphi(n) \), Euler's totient function; for \( n = 26 \), \( U_{26} = \{1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25\} \) has 12 elements<sup>[1](https://calc-path.com/abstract-algebra/modules/groups)</sup><sup> • </sup><sup>[4](https://zoo.cs.yale.edu/classes/cs467/2006f/attach/ln08.html)</sup> |
| Structure | \( (\mathbb{Z}/n\mathbb{Z})^{\times} \cong \prod_i (\mathbb{Z}/p_i^{r_i}\mathbb{Z})^{\times} \) over the prime factorization of \( n \)<sup>[5](https://perso.pages.math.cnrs.fr/users/diego.izquierdo/media/Polytechnique/Course_notes_final.pdf)</sup> |
| Prime powers | For odd \( p \), \( (\mathbb{Z}/p^r\mathbb{Z})^{\times} \) is cyclic of order \( p^{r-1}(p-1) \); \( (\mathbb{Z}/2^r\mathbb{Z})^{\times} \cong \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2^{r-2}\mathbb{Z} \)<sup>[5](https://perso.pages.math.cnrs.fr/users/diego.izquierdo/media/Polytechnique/Course_notes_final.pdf)</sup> |
| Cyclic cases | Primitive roots exist only for moduli \( 2, 4, p^a, 2p^a \) with \( p > 2 \) prime<sup>[6](https://encyclopediaofmath.org/wiki/Primitive_root)</sup> |
| Exponent | The Carmichael function \( \lambda(n) \), the least \( k \) with \( x^k \equiv 1 \pmod n \) for all \( x \) coprime to \( n \); \( \lambda(n) \) divides \( \varphi(n) \)<sup>[7](https://encyclopediaofmath.org/wiki/Carmichael_function)</sup> |
| Field criterion | \( \mathbb{Z}/n\mathbb{Z} \) is a field if and only if \( n \) is prime<sup>[8](https://www.youtube.com/watch?v=U_iutpWS2nE)</sup> |

## Definition and group structure

Let \( \mathbb{Z}/n\mathbb{Z} \) be the ring of residue classes of integers modulo \( n \). A unit is an element with a multiplicative inverse, and the units are precisely the classes \( [a] \) with \( \gcd(a, n) = 1 \). This condition is well defined on classes, because any two representatives of a class have the same gcd with the modulus.<sup>[3](https://www.math.gordon.edu/ntic/ntic2017/section-groups-numbers.html)</sup><sup> • </sup><sup>[9](https://www3.nd.edu/~sevens/znzstar.pdf)</sup>

The set of units is closed under multiplication: if \( \gcd(a, n) = \gcd(b, n) = 1 \), then \( \gcd(ab, n) = 1 \), which follows from [Bézout's identity](https://www.edgepedia.org/bezouts-identity) by writing \( ar + ns = 1 \) and \( bx + ny = 1 \) and multiplying the two equations.<sup>[9](https://www3.nd.edu/~sevens/znzstar.pdf)</sup> [Multiplication](https://www.edgepedia.org/multiplication) is associative and commutative because it is inherited from the integers, the identity is the class of 1, and the inverse of \( [a] \) is given by a class \( [x] \) with \( ax \equiv 1 \pmod n \), which exists by Bézout and is itself a unit. Hence \( (\mathbb{Z}/n\mathbb{Z})^{\times} \) is an abelian group.<sup>[9](https://www3.nd.edu/~sevens/znzstar.pdf)</sup><sup> • </sup><sup>[3](https://www.math.gordon.edu/ntic/ntic2017/section-groups-numbers.html)</sup>

Because the ring has exactly \( n \) residue classes, the group is finite, and its order is \( \varphi(n) \), the number of integers from 1 to \( n \) coprime to \( n \).<sup>[10](https://androma.org/theorems/11030)</sup><sup> • </sup><sup>[1](https://calc-path.com/abstract-algebra/modules/groups)</sup> When \( n \) is prime, every nonzero class is a unit, so \( \mathbb{Z}/n\mathbb{Z} \) is a field; conversely a field has no zero divisors, which forces \( n \) prime.<sup>[8](https://www.youtube.com/watch?v=U_iutpWS2nE)</sup>

## Decomposition by the Chinese remainder theorem

The Chinese remainder theorem gives a ring isomorphism \( \mathbb{Z}/n\mathbb{Z} \cong \prod_i \mathbb{Z}/p_i^{r_i}\mathbb{Z} \) for the prime factorization \( n = p_1^{r_1} \cdots p_s^{r_s} \). Ring isomorphisms preserve units, so the unit group splits accordingly:<sup>[5](https://perso.pages.math.cnrs.fr/users/diego.izquierdo/media/Polytechnique/Course_notes_final.pdf)</sup>

\[ (\mathbb{Z}/n\mathbb{Z})^{\times} \cong \prod_{i=1}^{s} (\mathbb{Z}/p_i^{r_i}\mathbb{Z})^{\times}. \]

This reduces the description of the group to prime-power moduli. It also yields the product formula for the totient function, \( \varphi(n) = \prod_i p_i^{r_i - 1}(p_i - 1) \), since the order of a product of groups is the product of the orders.<sup>[5](https://perso.pages.math.cnrs.fr/users/diego.izquierdo/media/Polytechnique/Course_notes_final.pdf)</sup>

## Prime-power moduli and primitive roots

For an odd prime \( p \) and \( r \ge 1 \), the group \( (\mathbb{Z}/p^r\mathbb{Z})^{\times} \) is cyclic of order \( p^{r-1}(p-1) \). A generator of this group is called a **primitive root** modulo \( p^r \): an integer \( g \) such that \( g^{\varphi(m)} \equiv 1 \pmod m \) and \( g^{\gamma} \not\equiv 1 \pmod m \) for \( 1 \le \gamma < \varphi(m) \). The powers \( g^0, \ldots, g^{\varphi(m)-1} \) then form a reduced system of residues, and every \( a \) coprime to \( m \) has an index, an exponent \( \gamma \) with \( g^{\gamma} \equiv a \pmod m \).<sup>[5](https://perso.pages.math.cnrs.fr/users/diego.izquierdo/media/Polytechnique/Course_notes_final.pdf)</sup><sup> • </sup><sup>[6](https://encyclopediaofmath.org/wiki/Primitive_root)</sup>

The case \( r = 1 \) rests on a general fact: any finite subgroup of the multiplicative group of a field is cyclic, proved by counting solutions of \( x^{n_1} = 1 \) in the structure decomposition of a finite abelian group.<sup>[5](https://perso.pages.math.cnrs.fr/users/diego.izquierdo/media/Polytechnique/Course_notes_final.pdf)</sup> For powers of 2 the group is not cyclic for \( r \ge 3 \): \( (\mathbb{Z}/2^r\mathbb{Z})^{\times} \cong \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2^{r-2}\mathbb{Z} \), with 5 of order \( 2^{r-2} \) supplying the second factor.<sup>[5](https://perso.pages.math.cnrs.fr/users/diego.izquierdo/media/Polytechnique/Course_notes_final.pdf)</sup> A concrete illustration is \( (\mathbb{Z}/8\mathbb{Z})^{\times} \), where \( x^2 \equiv 1 \pmod 8 \) for every odd \( x \), so no element generates the group and no primitive root modulo 8 exists.<sup>[11](https://ramanujan.math.trinity.edu/rdaileda/teach/s18/m3341/ZnZ.pdf)</sup>

Combining the two cases, primitive roots exist exactly for the moduli \( 2, 4, p^a, 2p^a \) with \( p > 2 \) prime; for these moduli the group of reduced residue classes is cyclic of order \( \varphi(m) \).<sup>[6](https://encyclopediaofmath.org/wiki/Primitive_root)</sup> A finite cyclic group of order \( n \) has exactly \( \varphi(n) \) generators, so when primitive roots exist modulo \( m \) there are \( \varphi(\varphi(m)) \) of them.<sup>[11](https://ramanujan.math.trinity.edu/rdaileda/teach/s18/m3341/ZnZ.pdf)</sup>

## The exponent: Carmichael's function

The **Carmichael function** \( \lambda(n) \) is the exponent of the group: the least positive \( \lambda \) such that \( a^{\lambda} \equiv 1 \pmod n \) for every \( a \) coprime to \( n \). The function is computed by taking the lcm of the values it takes at each prime-power divisor of \( n \): \( \lambda(n) = \mathrm{lcm}\{\lambda(p_i^{a_i})\} \).<sup>[7](https://encyclopediaofmath.org/wiki/Carmichael_function)</sup> Since the group order is \( \varphi(n) \), Lagrange's theorem gives \( \lambda(n) \mid \varphi(n) \). For odd prime powers \( \lambda(p^a) = \varphi(p^a) = p^{a-1}(p-1) \), while \( \lambda(2) = 1 \), \( \lambda(4) = 2 \), and \( \lambda(2^a) = 2^{a-2} \) for \( a \ge 3 \).<sup>[7](https://encyclopediaofmath.org/wiki/Carmichael_function)</sup> Equivalently, \( \lambda(n) \) is the largest order of any element of the group.<sup>[12](https://oeis.org/A002322)</sup>

The exponent matters in practice because a composite \( n \) with \( \lambda(n) \mid n - 1 \) is a [Carmichael number](https://www.edgepedia.org/carmichael-number), a composite that passes the Fermat primality test for every base coprime to \( n \); such numbers exist, so the test can prove compositeness but cannot prove primality.<sup>[7](https://encyclopediaofmath.org/wiki/Carmichael_function)</sup><sup> • </sup><sup>[13](https://oeis.org/wiki/Carmichael_numbers)</sup>

## Euler's theorem and cryptography

[Euler's theorem](https://www.edgepedia.org/eulers-theorem) states that \( x^{\varphi(n)} \equiv 1 \pmod n \) for every \( x \in (\mathbb{Z}/n\mathbb{Z})^{\times} \), with [Fermat's little theorem](https://www.edgepedia.org/fermats-little-theorem) \( x^{p-1} \equiv 1 \pmod p \) as the special case of prime modulus. A corollary is that \( a^r \equiv a^s \pmod n \) whenever \( r \equiv s \pmod{\varphi(n)} \) and \( a \) is a unit.<sup>[4](https://zoo.cs.yale.edu/classes/cs467/2006f/attach/ln08.html)</sup>

This corollary is the working principle of RSA: with modulus \( n = pq \) and keys satisfying \( ed \equiv 1 \pmod{\varphi(n)} \), decryption recovers the message because \( m^{ed} \equiv m \pmod n \) for \( m \in (\mathbb{Z}/n\mathbb{Z})^{\times} \).<sup>[4](https://zoo.cs.yale.edu/classes/cs467/2006f/attach/ln08.html)</sup> The same group underlies key-establishment schemes based on the discrete logarithm problem over finite fields, as specified in NIST SP 800-56A for Diffie-Hellman and MQV variants.<sup>[14](https://csrc.nist.gov/pubs/sp/800/56/a/r3/final)</sup>

## What the group looks like for small orders

The isomorphism type is not determined by \( \varphi(n) \) alone. For \( \varphi(n) = 8 \), the moduli \( n \in \{15, 16, 20, 24, 30\} \) all have eight units, but none of the resulting groups is cyclic; the cyclic group \( C_8 \) never occurs as a group of units modulo \( n \).<sup>[2](https://finitegroupdatabase.com/c/multiplicative)</sup> The classification follows from the prime-power decomposition: odd prime-power factors contribute cyclic groups, and a factor \( 2^r \) with \( r \ge 3 \) contributes the noncyclic product \( \mathbb{Z}/2 \times \mathbb{Z}/2^{r-2} \).<sup>[5](https://perso.pages.math.cnrs.fr/users/diego.izquierdo/media/Polytechnique/Course_notes_final.pdf)</sup>

## History

Primitive roots modulo a prime were introduced by [Leonhard Euler](https://www.edgepedia.org/leonhard-euler), and the existence of a primitive root modulo an arbitrary prime was demonstrated by [Carl Friedrich Gauss](https://www.edgepedia.org/carl-friedrich-gauss) in the *Disquisitiones Arithmeticae* of 1801, where primitive roots are treated in Article 57 and Gauss credited Euler with the term.<sup>[6](https://encyclopediaofmath.org/wiki/Primitive_root)</sup> The *Disquisitiones* also promoted the use of indices with respect to a fixed primitive root, in analogy with logarithm tables.<sup>[15](https://www.sophiararebooks.com/sep2018.pdf)</sup>

## References

1. [Definition 1.22 and Proposition 1.23, Abstract Algebra — Groups, calc-path.com](https://calc-path.com/abstract-algebra/modules/groups)
2. [Multiplicative group mod n, Finite Group Database](https://finitegroupdatabase.com/c/multiplicative)
3. [NTIC: Groups and Number Systems, Gordon College](https://www.math.gordon.edu/ntic/ntic2017/section-groups-numbers.html)
4. [Lecture notes 8: Modular exponentiation and Euler's theorem, Yale CS 467](https://zoo.cs.yale.edu/classes/cs467/2006f/attach/ln08.html)
5. [D. Izquierdo, Course notes, §3.1: The group of units of Z/nZ, École Polytechnique](https://perso.pages.math.cnrs.fr/users/diego.izquierdo/media/Polytechnique/Course_notes_final.pdf)
6. [Primitive root, Encyclopedia of Mathematics](https://encyclopediaofmath.org/wiki/Primitive_root)
7. [Carmichael function, Encyclopedia of Mathematics](https://encyclopediaofmath.org/wiki/Carmichael_function)
8. [AG07: The group of units of integers modulo n; Z/nZ a field iff n prime (video), Shahriari](https://www.youtube.com/watch?v=U_iutpWS2nE)
9. [The multiplicative group (Z/nZ)*, University of Notre Dame lecture notes](https://www3.nd.edu/~sevens/znzstar.pdf)
10. [Unit group modulo an integer is finite abelian, Androma](https://androma.org/theorems/11030)
11. [R. Daileda, The structure of (Z/nZ)×, Trinity University](https://ramanujan.math.trinity.edu/rdaileda/teach/s18/m3341/ZnZ.pdf)
12. [A002322: Reduced totient function (Carmichael lambda), OEIS](https://oeis.org/A002322)
13. [Carmichael numbers, OeisWiki](https://oeis.org/wiki/Carmichael_numbers)
14. [NIST SP 800-56A Rev. 3: Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography](https://csrc.nist.gov/pubs/sp/800/56/a/r3/final)
15. [Sophia Rare Books: Gauss, Disquisitiones Arithmeticae (1801), sale catalog description](https://www.sophiararebooks.com/sep2018.pdf)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Numbers and algebra › Number theory › Elementary number theory › Orders, primitive roots, and the multiplicative group mod n*

*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026; Oct 25, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license