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. [remark: Ratio for Prime Powers] For a fixed prime $p$, the ratio $\varphi(p^a)/p^a$ is always $1-1/p$. The exponent $a$ changes the scale of the count but not the density of integers coprime to $p^a$. [/remark] This local density viewpoint becomes especially useful once several prime divisors are present. Each distinct prime removes a proportion $1/p$ of residue classes, and the [Chinese remainder theorem](/theorems/734) explains why these removals multiply rather than add. ## Multiplicativity and the Product Formula ### Decomposing Coprime Moduli A modulus with several coprime factors can be studied one factor at a time. The reason is that congruence modulo $mn$ is equivalent to simultaneous congruence modulo $m$ and modulo $n$ when $m$ and $n$ are coprime, and the same decomposition respects multiplication of units. [quotetheorem:734] To name the coprime-product behavior produced by the Chinese [remainder theorem](/theorems/1707), we introduce a standard class of arithmetic functions. This language lets us say that $\varphi$ respects independent prime obstructions while also warning that the same product rule need not hold when the inputs share a factor. [definition: Multiplicative Arithmetic Function] An arithmetic function $f: \mathbb{N} \to \mathbb{C}$ is multiplicative if $f(1)=1$ and \begin{align*} f(mn)=f(m)f(n) \end{align*} for all $m,n \in \mathbb{N}$ with $\gcd(m,n)=1$. [/definition] Multiplicativity is weaker than requiring $f(mn)=f(m)f(n)$ for all $m,n$. That distinction matters for $\varphi$, since $\varphi(4)=2$ but $\varphi(2)\varphi(2)=1$. The Chinese remainder theorem gives a way to compare units modulo $mn$ with pairs of units modulo $m$ and modulo $n$, but only when the two moduli are coprime. Thus the real question is whether choosing a reduced residue modulo $m$ and one modulo $n$ determines a unique reduced residue modulo $mn$. When the prime obstructions are independent, it does; when they overlap, the example above shows that it cannot. [quotetheorem:7886] The hypothesis $\gcd(m,n)=1$ is doing real work here. It is not merely a technical condition attached to a convenient proof: it is what makes the prime obstructions in $m$ and $n$ independent, so that a unit modulo $mn$ can be recovered from its two unit components. If $m$ and $n$ share a prime factor, the same obstruction is present in both moduli, and multiplying the separate counts double-counts that obstruction rather than describing the units modulo the product. Thus multiplicativity is a rule for decomposing along coprime factors, not a universal product law for arbitrary factors. ### The Closed Formula Multiplicativity reduces all computations to prime powers, and the prime-power theorem supplies those local values. The next formula is the point where the abstract group count becomes a practical arithmetic expression in the prime factorisation of $n$. [quotetheorem:7887] The product formula says that the density of reduced residues modulo $n$ depends only on the distinct prime divisors of $n$, while the absolute size also depends on their exponents. [example: Computing $\varphi(360)$] Since \begin{align*} 360=36\cdot 10=(2^2\cdot 3^2)(2\cdot 5)=2^3\cdot 3^2\cdot 5, \end{align*} the distinct prime divisors of $360$ are $2,3,5$. By the *Product Formula for $\varphi$*, \begin{align*} \varphi(360)=360\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right). \end{align*} Each factor is \begin{align*} 1-\frac{1}{2}=\frac{1}{2},\qquad 1-\frac{1}{3}=\frac{2}{3},\qquad 1-\frac{1}{5}=\frac{4}{5}. \end{align*} Therefore \begin{align*} \varphi(360)=360\cdot \frac{1}{2}\cdot \frac{2}{3}\cdot \frac{4}{5}. \end{align*} Multiplying the factors in order, \begin{align*} 360\cdot \frac{1}{2}=180,\qquad 180\cdot \frac{2}{3}=120,\qquad 120\cdot \frac{4}{5}=96. \end{align*} Thus \begin{align*} \varphi(360)=96. \end{align*} So exactly $96$ residue classes modulo $360$ are coprime to $360$, equivalently $96$ residue classes modulo $360$ have multiplicative inverses. [/example] The formula is efficient once the factorisation of $n$ is known. It also reveals a computational warning: knowing $n$ alone is not the same as knowing $\varphi(n)$, because evaluating the product formula requires the prime divisors of $n$. [example: Why Coprimality of Factors is Needed] The product rule for $\varphi$ needs the condition $\gcd(m,n)=1$. Take $m=n=2$. Then $mn=4$, and the integers in $\{1,2,3,4\}$ coprime to $4$ are exactly \begin{align*} \{1,3\}. \end{align*} Indeed, $\gcd(1,4)=1$ and $\gcd(3,4)=1$, while $\gcd(2,4)=2$ and $\gcd(4,4)=4$. Hence \begin{align*} \varphi(4)=|\{1,3\}|=2. \end{align*} For each factor separately, the integers in $\{1,2\}$ coprime to $2$ are exactly \begin{align*} \{1\}, \end{align*} because $\gcd(1,2)=1$ and $\gcd(2,2)=2$. Therefore \begin{align*} \varphi(2)=|\{1\}|=1. \end{align*} Multiplying the two separate counts gives \begin{align*} \varphi(2)\varphi(2)=1\cdot 1=1. \end{align*} Thus \begin{align*} \varphi(4)=2\neq 1=\varphi(2)\varphi(2). \end{align*} The failure occurs because both factors contain the same prime obstruction $2$: treating the two copies of $2$ independently counts the loss of even residue classes twice. [/example] This failure example is the arithmetic shadow of the Chinese remainder theorem: the theorem decomposes a modulus only along coprime factors. Shared prime factors prevent independent reconstruction of residues. ## Euler's Theorem and Modular Exponents Once $\varphi(n)$ is recognised as the order of a finite group, exponent laws follow from finite group theory. The result is Euler's theorem, the main reason the totient function appears in congruence calculations. [quotetheorem:7888] Euler's theorem is best understood as the statement that every element of the finite group $(\mathbb{Z}/n\mathbb{Z})^\times$ has order dividing a common exponent, namely the group order. It generalises Fermat's little theorem from primes to arbitrary moduli. [quotetheorem:731] For prime moduli, $\varphi(p)=p-1$, so Fermat's theorem is the prime case of Euler's theorem. For composite moduli, the exponent $\varphi(n)$ can be much smaller than $n-1$. [example: Reducing Powers Modulo $15$] Since $15=3\cdot 5$ and $3,5$ are distinct primes, the *Product Formula for $\varphi$* gives \begin{align*} \varphi(15)=15\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right). \end{align*} The two factors are \begin{align*} 1-\frac{1}{3}=\frac{2}{3}\quad\text{and}\quad 1-\frac{1}{5}=\frac{4}{5}. \end{align*} Therefore \begin{align*} \varphi(15)=15\cdot\frac{2}{3}\cdot\frac{4}{5}. \end{align*} Multiplying in order, \begin{align*} 15\cdot\frac{2}{3}=5\cdot 2=10 \end{align*} and \begin{align*} 10\cdot\frac{4}{5}=2\cdot 4=8, \end{align*} so $\varphi(15)=8$. Also $\gcd(2,15)=1$, since the positive divisors of $2$ are $1,2$ and $2\nmid 15$. Hence *Euler's Theorem* gives \begin{align*} 2^8\equiv 1 \pmod{15}. \end{align*} Now \begin{align*} 2026=8\cdot 253+2 \end{align*} because $8\cdot 253=2024$. Thus \begin{align*} 2^{2026}=2^{8\cdot 253+2}. \end{align*} Using $x^{r+s}=x^rx^s$ and $(x^r)^s=x^{rs}$, \begin{align*} 2^{8\cdot 253+2}=(2^8)^{253}2^2. \end{align*} Reducing modulo $15$, \begin{align*} (2^8)^{253}2^2\equiv 1^{253}\cdot 4 \pmod{15}. \end{align*} Since $1^{253}=1$, \begin{align*} 1^{253}\cdot 4=4. \end{align*} Therefore \begin{align*} 2^{2026}\equiv 4 \pmod{15}. \end{align*} Euler's theorem reduces the large exponent modulo the period forced by the unit group, leaving only the small power $2^2$ to compute. [/example] The coprimality hypothesis cannot be removed. If $a$ shares a prime factor with $n$, powers of $a$ may move deeper into the non-unit part of the ring rather than returning to $1$. [example: Euler's Theorem Fails for Non-Units] Take $a=2$ and $n=8$. The integers in $\{1,\dots,8\}$ coprime to $8$ are exactly \begin{align*} 1,3,5,7. \end{align*} Indeed, each of $1,3,5,7$ is odd and shares no prime factor with $8=2^3$, while each of $2,4,6,8$ is divisible by $2$. Hence \begin{align*} \varphi(8)=|\{1,3,5,7\}|=4. \end{align*} Now \begin{align*} 2^{\varphi(8)}=2^4=2\cdot 2\cdot 2\cdot 2=16. \end{align*} Since \begin{align*} 16=2\cdot 8+0, \end{align*} we have \begin{align*} 16\equiv 0 \pmod{8}. \end{align*} Therefore \begin{align*} 2^{\varphi(8)}\equiv 0 \pmod{8}, \end{align*} not $1 \pmod{8}$. The obstruction is that $\bar{2}$ is not a unit modulo $8$: for every integer $b$, the product $2b$ is even, so $2b-1$ is odd and cannot be divisible by $8$; hence $2b\not\equiv 1\pmod{8}$. Euler's theorem applies to units, and this example shows why the coprimality hypothesis is necessary. [/example] This is the same obstruction seen at the beginning of the chapter. The totient function governs the invertible part of modular arithmetic, not the whole residue ring. ## Divisor Sums and Counting by Denominator The product formula describes $\varphi(n)$ through prime factorisation. There is another description that counts all residues by the value of their greatest common divisor with $n$. If the fraction $k/n$ is reduced, its final denominator is a divisor of $n$, and the numerators that reduce to denominator $d$ are exactly the residues coprime to $d$. Thus the residues split into classes counted by $\varphi(d)$, giving the divisor-sum identity \begin{align*} \sum_{d\mid n}\varphi(d)=n. \end{align*} This identity partitions the integers $1,\dots,n$ according to the denominator that remains after reducing the fraction $k/n$. It gives a different way to see why $\varphi$ is a natural counting function before introducing the more algebraic language of convolution and inversion below. [example: Divisor Sum for $12$] The positive divisors of $12$ are $1,2,3,4,6,12$. Using the definition of $\varphi$, the reduced representatives for these moduli are \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*} \begin{align*} \{k\in\{1,2,3,4\}:\gcd(k,4)=1\}=\{1,3\}, \end{align*} \begin{align*} \{k\in\{1,\dots,6\}:\gcd(k,6)=1\}=\{1,5\}, \end{align*} and \begin{align*} \{k\in\{1,\dots,12\}:\gcd(k,12)=1\}=\{1,5,7,11\}. \end{align*} Therefore \begin{align*} \varphi(1)=1,\quad \varphi(2)=1,\quad \varphi(3)=2,\quad \varphi(4)=2,\quad \varphi(6)=2,\quad \varphi(12)=4. \end{align*} Adding these values gives \begin{align*} \varphi(1)+\varphi(2)+\varphi(3)+\varphi(4)+\varphi(6)+\varphi(12)=1+1+2+2+2+4. \end{align*} Now \begin{align*} 1+1+2+2+2+4=2+2+2+2+4=4+2+2+4=6+2+4=8+4=12. \end{align*} Hence \begin{align*} \sum_{d\mid 12}\varphi(d)=12. \end{align*} The term $\varphi(12)=4$ counts the four fractions with denominator $12$ in lowest terms, represented by $1/12,5/12,7/12,11/12$; the remaining terms count fractions whose denominator becomes one of the proper divisors $1,2,3,4,6$ after cancellation. [/example] The divisor-sum identity has the form of a sum over all divisors of $n$. To manipulate such identities systematically, we need an operation on arithmetic functions whose multiplication law is built from divisor pairs. [definition: Dirichlet Convolution] For arithmetic functions $f,g: \mathbb{N} \to \mathbb{C}$, their Dirichlet convolution is the arithmetic function $f*g:\mathbb{N}\to\mathbb{C}$ defined by \begin{align*} (f*g)(n)=\sum_{d\mid n} f(d)g(n/d). \end{align*} [/definition] To make the divisor-sum theorem reusable, we now translate it into the algebra of convolution. Let $\operatorname{id}:\mathbb{N}\to\mathbb{N}$ denote $\operatorname{id}(n)=n$, and let $1:\mathbb{N}\to\mathbb{N}$ denote the constant function $1(n)=1$; with these names, the identity becomes a single convolution equation. The inverse operation for this kind of divisor sum is controlled by a signed arithmetic function, so we define that function before using the convolution identity. [definition: Mobius Function] The Mobius function is the arithmetic function $\mu:\mathbb{N}\to\{-1,0,1\}$ with $\mu(1)=1$, with $\mu(n)=(-1)^r$ when $n=p_1\cdots p_r$ for distinct primes $p_1,\dots,p_r$, and with $\mu(n)=0$ when $p^2\mid n$ for some prime $p$. [/definition] With $\mu$ available, the divisor-sum theorem can be stated in the convolution language used for inversion formulas. This is the point at which $\varphi$ begins to behave not just as a counting function, but as an arithmetic function that can be multiplied and inverted through divisor sums. The next useful step is to identify exactly which convolution equation the earlier divisor-sum identity represents. Once that equation is isolated, it becomes possible to apply the standard inverse of the constant function and solve back for $\varphi(n)$ in terms of the divisors of $n$. [quotetheorem:4343] This identity is useful because it separates two different kinds of information. The left side packages the local counts $\varphi(d)$ over all divisors of $n$, while the right side is the much simpler function $\operatorname{id}(n)=n$. For example, when $n=12$, the equation says that $\varphi(1)+\varphi(2)+\varphi(3)+\varphi(4)+\varphi(6)+\varphi(12)=12$, so the totient values are not isolated facts: together they form a divisor-sum system. The limitation is that this convolution equation does not by itself give a closed formula for $\varphi(n)$; it gives $\varphi$ only after it has been summed against the constant function $1$. Its real role is therefore algebraic. Once the identity is written as $\varphi * 1=\operatorname{id}$, one can undo the summation by convolving with the inverse of $1$. The Mobius function plays that inverse role, so the next formula rewrites the totient as an inclusion-exclusion sum over the divisors of $n$. [quotetheorem:7889] This formula subtracts the contributions of integers divisible by each prime divisor of $n$, then adds back the intersections, exactly as inclusion-exclusion predicts. ## Structure of the Unit Group The number $\varphi(n)$ gives the size of the unit group, but size alone does not describe the group. Two moduli can have unit groups of the same order and different structure. A natural next question asks whether all units can be generated by powers of a single residue class. [definition: Primitive Root Modulo $n$] Let $n \in \mathbb{N}$. A primitive root modulo $n$ is an integer $g \in \mathbb{Z}$ such that the residue class $\bar{g}$ generates the group $(\mathbb{Z}/n\mathbb{Z})^\times$. [/definition] A primitive root exists exactly when the unit group is cyclic. To test whether a candidate generator works, we need to measure the period of its successive powers modulo $n$. [definition: Order of a Unit Modulo $n$] Let $n \in \mathbb{N}$. The order map modulo $n$ is the function $\operatorname{ord}_n:(\mathbb{Z}/n\mathbb{Z})^\times\to\mathbb{N}$ defined by \begin{align*} \operatorname{ord}_n(\bar{a})=\min\{k\in\mathbb{N}:a^k\equiv 1\pmod n\}. \end{align*} [/definition] The order of a unit is defined as a first return time, but a priori that period could seem unrelated to the total number of units. To test primitive roots efficiently, we need a restriction on which return times are possible. The finite group structure supplies that restriction: every multiplicative period must fit inside the size $\varphi(n)$ of the unit group. [quotetheorem:841] This theorem explains how $\varphi(n)$ bounds every possible multiplicative period modulo $n$. Primitive roots are the case where the bound is attained. [example: A Primitive Root Modulo $7$] Modulo $7$, compute the successive powers of $3$ until the first return to $1$. The first power is \begin{align*} 3^1=3, \end{align*} so $3^1\equiv 3\pmod{7}$. Next, \begin{align*} 3^2=9=1\cdot 7+2, \end{align*} so $3^2\equiv 2\pmod{7}$, and \begin{align*} 3^3=3\cdot 3^2\equiv 3\cdot 2=6\pmod{7}. \end{align*} Continuing from the previous residues, \begin{align*} 3^4=3\cdot 3^3\equiv 3\cdot 6=18=2\cdot 7+4\pmod{7}, \end{align*} so $3^4\equiv 4\pmod{7}$. Also \begin{align*} 3^5=3\cdot 3^4\equiv 3\cdot 4=12=1\cdot 7+5\pmod{7}, \end{align*} so $3^5\equiv 5\pmod{7}$, and \begin{align*} 3^6=3\cdot 3^5\equiv 3\cdot 5=15=2\cdot 7+1\pmod{7}. \end{align*} Thus $3^6\equiv 1\pmod{7}$. The residues obtained before returning to $1$ are \begin{align*} 3,2,6,4,5,1, \end{align*} which are exactly the six nonzero residue classes modulo $7$. Therefore the powers of $\bar{3}$ generate $(\mathbb{Z}/7\mathbb{Z})^\times$, so $3$ is a primitive root modulo $7$ and $\operatorname{ord}_7(\bar{3})=6=\varphi(7)$. [/example] Not every modulus has a primitive root. The unit group modulo $8$ already shows the obstruction: every unit squares to $1$, so no element can generate all four units. [example: No Primitive Root Modulo $8$] The units modulo $8$ are $\bar{1},\bar{3},\bar{5},\bar{7}$, because the representatives in $\{1,\dots,8\}$ coprime to $8$ are exactly \begin{align*} \{1,3,5,7\}. \end{align*} Indeed, $1,3,5,7$ are odd, while $2,4,6,8$ are divisible by $2$ and therefore share the common divisor $2$ with $8$. Now compute the square of each unit. First, \begin{align*} 1^2=1, \end{align*} so $1^2\equiv 1\pmod{8}$. Also, \begin{align*} 3^2=9=1\cdot 8+1, \end{align*} so $3^2\equiv 1\pmod{8}$. Similarly, \begin{align*} 5^2=25=3\cdot 8+1, \end{align*} so $5^2\equiv 1\pmod{8}$, and \begin{align*} 7^2=49=6\cdot 8+1, \end{align*} so $7^2\equiv 1\pmod{8}$. Thus every unit modulo $8$ satisfies $\bar{a}^2=\bar{1}$. The class $\bar{1}$ has order $1$, and each of $\bar{3},\bar{5},\bar{7}$ has order $2$, since its first power is not $\bar{1}$ but its square is $\bar{1}$. Hence no unit has order $4$. Since \begin{align*} \varphi(8)=|\{1,3,5,7\}|=4, \end{align*} a primitive root modulo $8$ would have to generate all four units. But the powers of any unit return to $\bar{1}$ after at most two steps, so they produce at most two distinct classes. Therefore there is no primitive root modulo $8$. [/example] The complete classification of moduli with primitive roots identifies exactly when the unit group is cyclic. This statement is deeper than the basic totient identities, but it marks the boundary between knowing only the size $\varphi(n)$ and knowing that a single unit controls the entire multiplicative group. [quotetheorem:7890] This theorem shows that cyclic unit groups are special rather than universal. The totient function still gives the size of the group for every modulus, but the internal shape of that group can vary substantially. ## Applications and Computational Meaning ### Fast Exponent Computations The totient function enters algorithms through exponent reduction. If an exponent is large and the base is coprime to the modulus, Euler's theorem lets us remove whole multiples of $\varphi(n)$ from the exponent. When the remaining exponent is $0$, this means replacing $a^k$ by $1$ using $a^{\varphi(n)}\equiv 1\pmod n$, not by treating $a^0$ as though it recorded the original power. [example: Exponent Reduction with a Composite Modulus] Let $n=21$ and compute $5^{1000}$ modulo $21$. Since \begin{align*} 21=3\cdot 7, \end{align*} the distinct prime divisors of $21$ are $3$ and $7$. By the *Product Formula for $\varphi$*, \begin{align*} \varphi(21)=21\left(1-\frac{1}{3}\right)\left(1-\frac{1}{7}\right). \end{align*} The two factors are \begin{align*} 1-\frac{1}{3}=\frac{2}{3} \end{align*} and \begin{align*} 1-\frac{1}{7}=\frac{6}{7}. \end{align*} Therefore \begin{align*} \varphi(21)=21\cdot \frac{2}{3}\cdot \frac{6}{7}. \end{align*} Multiplying in order, \begin{align*} 21\cdot \frac{2}{3}=7\cdot 2=14 \end{align*} and \begin{align*} 14\cdot \frac{6}{7}=2\cdot 6=12, \end{align*} so $\varphi(21)=12$. Also \begin{align*} 21=4\cdot 5+1, \end{align*} so $\gcd(5,21)=1$. Hence [Fermat-Euler Theorem](/theorems/732) gives \begin{align*} 5^{12}\equiv 1\pmod{21}. \end{align*} Now \begin{align*} 12\cdot 83=996 \end{align*} and therefore \begin{align*} 1000=12\cdot 83+4. \end{align*} Using $x^{r+s}=x^rx^s$ and $(x^r)^s=x^{rs}$, \begin{align*} 5^{1000}=5^{12\cdot 83+4}=(5^{12})^{83}5^4. \end{align*} Reducing modulo $21$ gives \begin{align*} (5^{12})^{83}5^4\equiv 1^{83}5^4\pmod{21}. \end{align*} Since $1^{83}=1$, \begin{align*} 5^{1000}\equiv 5^4\pmod{21}. \end{align*} It remains to compute the small power. First, \begin{align*} 5^2=25=1\cdot 21+4, \end{align*} so $5^2\equiv 4\pmod{21}$. Hence \begin{align*} 5^4=(5^2)^2\equiv 4^2\pmod{21}. \end{align*} Finally, \begin{align*} 4^2=16, \end{align*} so \begin{align*} 5^{1000}\equiv 16\pmod{21}. \end{align*} Euler's theorem removes the $83$ full blocks of length $\varphi(21)=12$, leaving only the residue of the exponent, namely $4$, to compute. [/example] ### RSA and Factorisation In public-key cryptography, the practical point is sharper: for $n=pq$ with distinct large primes, $\varphi(n)=(p-1)(q-1)$. Knowing the factorisation gives $\varphi(n)$, while practical RSA parameters are chosen so that recovering the factorisation from $n$ is computationally infeasible with known methods. This is a security assumption about suitable large instances, not a theorem of elementary number theory. The following congruence is the algebraic core behind the exponent step. [quotetheorem:7891] The displayed congruence is the algebraic core of RSA for units modulo $n$. Full cryptographic schemes include padding, message encoding, side-channel protections, and security reductions; the totient function supplies the modular exponent identity. The same formula also explains why revealing $\varphi(pq)$ is dangerous when $p$ and $q$ are unknown. Since \begin{align*} \varphi(pq)=pq-p-q+1, \end{align*} knowing both $n=pq$ and $\varphi(n)$ gives the sum $p+q=n-\varphi(n)+1$, and then $p$ and $q$ are roots of a quadratic polynomial. [example: Recovering Factors from $n$ and $\varphi(n)$] Suppose $n=55$ and $\varphi(n)=40$, with $n=pq$ for distinct primes $p$ and $q$. Since $n=pq$, the product formula for two distinct primes gives \begin{align*} \varphi(n)=\varphi(pq)=(p-1)(q-1). \end{align*} Expanding the right-hand side, \begin{align*} (p-1)(q-1)=pq-p-q+1. \end{align*} Substituting $pq=n$ gives \begin{align*} \varphi(n)=n-p-q+1. \end{align*} Rearranging, \begin{align*} p+q=n-\varphi(n)+1. \end{align*} With $n=55$ and $\varphi(n)=40$, \begin{align*} p+q=55-40+1=16. \end{align*} Thus $p$ and $q$ have product $55$ and sum $16$. Therefore they are the two roots of \begin{align*} t^2-(p+q)t+pq=0, \end{align*} which becomes \begin{align*} t^2-16t+55=0. \end{align*} Factoring, \begin{align*} t^2-16t+55=(t-5)(t-11), \end{align*} because \begin{align*} (t-5)(t-11)=t^2-11t-5t+55=t^2-16t+55. \end{align*} Hence the roots are $5$ and $11$, so \begin{align*} \{p,q\}=\{5,11\}. \end{align*} Knowing both $n$ and $\varphi(n)$ recovers the sum and product of the two prime factors, and those two numbers determine the factors. [/example] The computational lesson is that $\varphi$ is not just a function attached to $n$; it encodes prime-factor information. That is why the same object belongs both to elementary counting and to modern computational number theory. ## Beyond and Connected Topics The Euler totient function is the entry point to arithmetic functions. Dirichlet convolution, Mobius inversion, divisor sums, and multiplicativity form a small algebraic world in which $\varphi$ is one of the central examples. From here, the divisor function, sum-of-divisors functions, the Mobius function, and Dirichlet series become natural next objects; the course-level continuation is [Cambridge IA Numbers and Sets](/page/Cambridge%20IA%20Numbers%20and%20Sets), where divisibility, congruences, and prime factorisation provide the background for these counting arguments. The group $(\mathbb{Z}/n\mathbb{Z})^\times$ leads from elementary number theory into algebra. Its decomposition through the Chinese remainder theorem uses the same product philosophy that appears in [Cambridge IB Linear Algebra](/page/Cambridge%20IB%20Linear%20Algebra), where structure is understood by decomposing objects into simpler pieces. Primitive roots then ask when this finite abelian group is cyclic, so the subject naturally continues toward finite abelian groups, cyclic groups, and the structure of units in quotient rings. The analytic side begins when one studies average orders such as the size of $\sum_{n\le x}\varphi(n)$. At that point the totient function is no longer only a modular counting function: it becomes a test case for estimating sums of multiplicative functions, using Dirichlet convolution as an algebraic shadow of prime factorisation. The modular-exponent side connects to cryptography and computational algebra. Euler's theorem gives exponent reduction, while RSA uses the special case $n=pq$. The security meaning comes not from the formal congruence alone but from the difficulty of recovering $\varphi(n)$ without factoring $n$. ## References This introductory note is self-contained; its theorem cards and cited proof accordions provide the internal references used above. - Androma, [Cambridge IA Numbers and Sets](/page/Cambridge%20IA%20Numbers%20and%20Sets). - Androma, [Cambridge IB Linear Algebra](/page/Cambridge%20IB%20Linear%20Algebra). - Hardy and Wright, *An Introduction to the Theory of Numbers* (1938). - Ireland and Rosen, *A Classical Introduction to Modern Number Theory* (1982). - Apostol, *Introduction to Analytic Number Theory* (1976).