Multiplicative group of integers
Summary
Although Z/n\mathbb Z / n does not generally form a group under multiplcation, (Z/n)×(\mathbb Z / n)^\times—i.e., only those aZ/na \in \mathbb Z / n coprime with nn—does. This group is called the multiplicative group of integers mod nn and is denoted (Z/n)×(\mathbb Z / n)^\times.
Idea
Generally we know that the structure (Z/n,+)(\mathbb Z / n, +)—that is, integers modulo nn under addition—forms a group. What about (Z/n,)(\mathbb Z / n, \cdot), the integers modulo nn under multiplication? No: inverses will be lacking for 0ˉ\bar 0 as well as every element aZ/na \in \mathbb Z / n sharing a factor with nn pf. Perhaps, then, if we take only the subset of Z/n\mathbb Z / n consisting of elements coprime with nn, we would get a group?
Fix nn, aa. Want to show that it’s contradictory for aa to be coprime with nn and yet not have an inverse (mod nn). This entails that aa is coprime with nn iff it has an inverse (mod nn). Assume aa and nn are not coprime. Then exists some c1,ca,cnc \neq 1, c_a, c_n with a=ccaa = c \cdot c_a and n=ccnn = c\cdot c_n. Also assume that aa has an inverse (mod nn); that is, that exists some pp with apn1a^p \equiv_n 1. By definition of n\equiv_n, this means that there is some kk where ap=1+kna^p = 1 + kn. Then we have: ap=1+kn(cca)p=1+kccn(cca)pkccn=1c(cp1capkcn)=1\begin{align*} a^p &= 1+kn \\ (cc_a)^p &= 1 + kcc_n \\ (cc_a)^p - kcc_n &= 1 \\ c(c^{p-1}c_a^p - kc_n) &= 1 \end{align*} Since both terms in the left-hand side product are integral, and since their product is one, then they must both be one. However, by assumption, c1c \neq 1. Contradiction.
As it turns out, this works! Proof below.
Proof
Fix nn. Let (Z/n)×(\mathbb Z / n)^\times denote the set of integers 1a<n1 \leq a < n coprime with nn, all taken modulo nn. We claim that (Z/n)×(\mathbb Z / n)^\times forms a group under multiplication:
1. Closure: given aˉ,bˉ\bar a, \bar b in (Z/n)×(\mathbb Z / n)^\times that aˉbˉ\bar a \cdot \bar b is also in (Z/n)×(\mathbb Z / n)^\times pf.
Intuition. The product of two integers coprime with nn is still coprime with nn, and that holds in modular systems as well. Proof. Take aˉ,bˉ(Z/n)×\bar a, \bar b \in (\mathbb Z / n)^\times. Let a,ba, b be the unique representatives of aˉ,bˉ\bar a, \bar b that lie within [0,n)[0, n). Since aˉ,bˉ(Z/n)×\bar a, \bar b \in (\mathbb Z / n)^\times then a,ba,b are coprime with nn, and thus so is abab pf. Since abab is coprime with nn, then mod(ab,n)\text{mod}(ab, n) is, as well pf. Since mod(ab,n)\text{mod}(ab, n) is coprime with nn, and since 0mod(ab,n)<n0 \leq \text{mod}(ab, n) < n, we have that mod(ab,n)(Z/n)×\overline{\text{mod}(ab, n)} \in (\mathbb Z / n)^\times. Finally, by rules of modular arithmetic, aˉbˉ=ab=mod(ab,n)\bar a \cdot \bar b = \overline{ab} = \overline{\text{mod}(ab, n)}; thus, ab(Z/n)×\overline{ab} \in (\mathbb Z / n)^\times.
Prop. If a,bZa, b \in \mathbb Z are coprime with nn, then abab is coprime with nn. Proof. Take a,ba, b. Assume for contradiction that abab is not coprime with nn. Then exists some f2f \geq 2 dividing both abab and nn. Since ff divides abab, then it must divide either aa or bb, which makes either aa or bb share a factor with nn; contradiction.
Prop. If xx is coprime with nn, then mod(x,n)\text{mod}(x, n) is coprime with nn. Proof. Note that for some kk we have x=nk+mod(x,n)x = nk + \text{mod}(x, n). Now assume for contradiction that mod(x,n)\text{mod}(x, n) shares a factor ff with nn. Then we have mod(x,n)=fκ1\text{mod}(x, n) = f\kappa_1 and n=fκ2n = f\kappa_2 for some κ1,κ2\kappa_1, \kappa_2. Plugging this into x=nk+mod(x,n)x = nk + \text{mod}(x, n) we get x=(fκ2)k+fκ1=f(κ2k+κ1)x = (f\kappa_2)k + f\kappa_1 = f(\kappa_2k+\kappa_1). Thus fxf \mid x, meaning that it is not coprime with nn; contradiction.
2. Associativity: (aˉbˉ)cˉ=aˉ(bˉcˉ)(\bar a \cdot \bar b) \cdot \bar c = \bar a \cdot (\bar b \cdot \bar c) pf.
Know by properties of modular arithmetic that aˉbˉ=ab\bar a \cdot \bar b = \overline{a \cdot b}; associativity follows.
3. Identity: for every a(Z/n)×a \in (\mathbb Z / n)^\times we have 1ˉaˉ=aˉ1ˉ=aˉ\bar 1 \cdot \bar a = \bar a \cdot \bar 1 = \bar a pf.
This follows from the fact that aˉbˉ=ab\bar a \cdot \bar b = \overline{a \cdot b}.
4. Inverses: given any aˉ(Z/n)×\bar a \in (\mathbb Z / n)^\times exists a bˉ\bar b such that aˉbˉ=bˉaˉ=1ˉ\bar a \cdot \bar b = \bar b \cdot \bar a = \bar 1 pf.
Take aˉ(Z/n)×\bar a \in (\mathbb Z /n)^\times, and let aaˉa \in \bar a be your choice of representative. We know that aa is coprime with nn, which by Bezout's identity guarantees x,yZx, y \in \mathbb Z such that ax+ny=1ax + ny = 1. This rearranges to ax=(ny)+1ax = (-ny) + 1, meaning that axn1ax \equiv_n 1 since nnyn \mid -ny. Likewise, xan1xa \equiv_n 1; thus xˉ\bar x is the inverse of aˉ\bar a.



Referenced by: