Counting residue classes modulo $n$ is often the first place where finite arithmetic stops behaving like arithmetic in a field. Here $\mathbb{Z}/n\mathbb{Z}$ denotes the set of congruence classes modulo $n$, and $\bar{a}$ denotes the class of all integers congruent to $a$ modulo $n$. Modulo $7$, every nonzero class has a multiplicative inverse, so cancellation and division work. Modulo $12$, the class $\bar{6}$ is nonzero but cannot be inverted, and multiplying by $\bar{6}$ collapses information: $\bar{6}\bar{1}=\bar{6}\bar{3}$ in $\mathbb{Z}/12\mathbb{Z}$ because $6\equiv 18\pmod{12}$. The Euler totient function measures exactly how much multiplicative arithmetic survives after passing from the integers to residues modulo $n$.

The central question is not only "how many numbers are coprime to $n$?" but also "how large is the multiplicative group modulo $n$?" This number controls modular exponentiation, cyclicity questions, primitive roots, RSA-style congruences, and many counting arguments in elementary number theory. It also gives a first example of an arithmetic function whose structure is determined by prime factorisation.

[example: Failure of Division Modulo $12$] In $\mathbb{Z}/12\mathbb{Z}$, the class $\bar{5}$ is invertible because \begin{align*} 5\cdot 5=25=2\cdot 12+1, \end{align*} so $5\cdot 5\equiv 1\pmod{12}$. Thus $\bar{5}^{-1}=\bar{5}$. The class $\bar{6}$ is not invertible. If $\bar{6}$ had an inverse, then for some $a\in\mathbb{Z}$ we would have \begin{align*} 6a\equiv 1\pmod{12}. \end{align*} This means $12\mid 6a-1$, so $6a-1=12q$ for some $q\in\mathbb{Z}$. The right-hand side $12q$ is even, while \begin{align*} 6a-1=2(3a)-1 \end{align*} is odd, a contradiction. The invertible residue classes modulo $12$ are exactly \begin{align*} \bar{1},\bar{5},\bar{7},\bar{11}. \end{align*} Their inverses are visible from \begin{align*} 1\cdot 1=1,\quad 5\cdot 5=25\equiv 1,\quad 7\cdot 7=49\equiv 1,\quad 11\cdot 11=121\equiv 1\pmod{12}. \end{align*} The remaining nonzero classes fail to be units because each product with $12$ has a common divisor greater than $1$: $2,4,6,8,10$ are even, $3$ and $9$ are divisible by $3$, and none of these classes can multiply to $\bar{1}$ modulo $12$. Therefore the invertible part of $\mathbb{Z}/12\mathbb{Z}$ has four elements. [/example]

This example shows why the right counting problem is not the number of nonzero residues. The residues $\bar{2},\bar{3},\bar{4},\bar{6},\bar{8},\bar{9},\bar{10}$ are nonzero modulo $12$, but each shares a factor with $12$ and fails to be a unit. The totient function isolates the residue classes that avoid every prime obstruction in $n$.

## Definition

The basic object counts integers in a complete residue system that have no common prime factor with the modulus. The interval $\{1,\dots,n\}$ is a convenient representative system, and using $\gcd$ makes the definition independent of any particular representatives in $\mathbb{Z}/n\mathbb{Z}$.

[definition: Euler Totient Function] The Euler totient function is the arithmetic function $\varphi: \mathbb{N}\to \mathbb{N}$ defined by \begin{align*} \varphi(n)=\left|\{k \in \{1,\dots,n\} : \gcd(k,n)=1\}\right|. \end{align*} [/definition]

Counting coprime representatives is not enough when we want to multiply or divide congruence classes. A residue class can be cancelled in modular arithmetic only when it has a multiplicative inverse, and not every class has one: for example, an even class modulo an even modulus cannot be inverted. The following definition isolates exactly the classes for which division makes sense.

[definition: Unit Group Modulo $n$] For $n \in \mathbb{N}$, the unit group modulo $n$ is \begin{align*} (\mathbb{Z}/n\mathbb{Z})^\times = \{\bar{a} \in \mathbb{Z}/n\mathbb{Z} : \exists\,\bar{b} \in \mathbb{Z}/n\mathbb{Z}\text{ with }\bar{a}\bar{b}=\bar{1}\}. \end{align*} [/definition]

The definition of a unit uses multiplication in the residue ring, while the definition of $\varphi(n)$ uses the integer condition $\gcd(a,n)=1$. The next result is the dictionary between these two languages, and it is the reason the totient function is a group order rather than only a list of coprime representatives.

[quotetheorem:7884]

This theorem converts a counting function into a group order. From this point on, every group-theoretic fact about finite groups gives a congruence statement for integers coprime to $n$.

[example: First Values of $\varphi$] Using the definition of $\varphi(n)$, we count the integers $k\in\{1,\dots,n\}$ with $\gcd(k,n)=1$. For the first four moduli, \begin{align*} \{k\in\{1\}:\gcd(k,1)=1\}=\{1\}, \end{align*} \begin{align*} \{k\in\{1,2\}:\gcd(k,2)=1\}=\{1\}, \end{align*} \begin{align*} \{k\in\{1,2,3\}:\gcd(k,3)=1\}=\{1,2\}, \end{align*} and \begin{align*} \{k\in\{1,2,3,4\}:\gcd(k,4)=1\}=\{1,3\}. \end{align*} Therefore \begin{align*} \varphi(1)=1,\quad \varphi(2)=1,\quad \varphi(3)=2,\quad \varphi(4)=2. \end{align*} Continuing in the same way, \begin{align*} \{k\in\{1,\dots,5\}:\gcd(k,5)=1\}=\{1,2,3,4\}, \end{align*} \begin{align*} \{k\in\{1,\dots,6\}:\gcd(k,6)=1\}=\{1,5\}, \end{align*} \begin{align*} \{k\in\{1,\dots,7\}:\gcd(k,7)=1\}=\{1,2,3,4,5,6\}, \end{align*} and \begin{align*} \{k\in\{1,\dots,8\}:\gcd(k,8)=1\}=\{1,3,5,7\}. \end{align*} Thus \begin{align*} \varphi(5)=4,\quad \varphi(6)=2,\quad \varphi(7)=6,\quad \varphi(8)=4. \end{align*} For the last three listed values, the reduced representatives are \begin{align*} \{k\in\{1,\dots,9\}:\gcd(k,9)=1\}=\{1,2,4,5,7,8\}, \end{align*} \begin{align*} \{k\in\{1,\dots,10\}:\gcd(k,10)=1\}=\{1,3,7,9\}, \end{align*} and \begin{align*} \{k\in\{1,\dots,12\}:\gcd(k,12)=1\}=\{1,5,7,11\}. \end{align*} Hence \begin{align*} \varphi(9)=6,\quad \varphi(10)=4,\quad \varphi(12)=4. \end{align*} The prime moduli $2,3,5,7$ keep every representative except the modulus itself, while the composite moduli lose exactly those representatives sharing a prime factor with the modulus. [/example]

These examples suggest that prime factorisation should control the function. The rest of the chapter develops that principle and then uses it to explain the exponent laws behind modular arithmetic.

## Prime Powers and the Local Count

The cleanest case is a prime power. If $n=p^a$, the only obstruction to being coprime to $n$ is divisibility by $p$. This is the local building block for the general formula.

[quotetheorem:7885]

The formula removes the multiples of $p$ from the $p^a$ possible residue representatives. It also shows that passing from $p^{a-1}$ to $p^a$ multiplies the count by $p$, except for the first appearance of the prime.

[example: Powers of $2$] For $a \in \mathbb{N}$, the integers in $\{1,\dots,2^a\}$ that are not coprime to $2^a$ are exactly the even ones. They are \begin{align*} 2,4,6,\dots,2^a. \end{align*} Writing each as $2j$, this list corresponds to \begin{align*} j=1,2,\dots,2^{a-1}, \end{align*} so there are $2^{a-1}$ even integers in $\{1,\dots,2^a\}$. Therefore \begin{align*} \varphi(2^a)=2^a-2^{a-1}. \end{align*} Factoring out $2^{a-1}$ gives \begin{align*} 2^a-2^{a-1}=2\cdot 2^{a-1}-1\cdot 2^{a-1}=(2-1)2^{a-1}=2^{a-1}. \end{align*} Thus exactly half of the residue classes modulo $2^a$ are units, namely the odd classes. For $a=4$, we have $2^4=16$. The odd representatives in $\{1,\dots,16\}$ are \begin{align*} 1,3,5,7,9,11,13,15. \end{align*} Each has greatest common divisor $1$ with $16$, while every even representative shares the common divisor $2$ with $16$. Hence the units modulo $16$ are \begin{align*} \bar{1},\bar{3},\bar{5},\bar{7},\bar{9},\bar{11},\bar{13},\bar{15}. \end{align*} [/example]

Prime powers also show why $\varphi(n)$ is not usually close to $n-1$. Large repeated prime factors do not introduce new forbidden primes, but they do enlarge the modulus and therefore enlarge the set of reduced residues proportionally.