Reduced Residue Systems and the Totient Function

Reduced residue systems and $\varphi(n)$ are the quiet engine behind RSA public-key cryptography: choosing $n = pq$ for distinct primes $p, q$, one uses $\varphi(n) = (p-1)(q-1)$ to construct encryption/decryption exponents that are inverses modulo $\varphi(n)$, and Euler's theorem (proved above via the permutation property) guarantees correct decryption. In computational number theory, fast algorithms for primality testing and factoring lean on the group structure of $(\mathbb{Z}/n\mathbb{Z})^{\times}$ established here. In combinatorics, $\varphi(n)$ appears in counting formulas for cyclic groups (the number of generators of a cyclic group of order $n$ is exactly $\varphi(n)$), in the theory of cyclotomic polynomials (the degree of the $n$-th cyclotomic polynomial is $\varphi(n)$), and in analytic number theory through the average order and Dirichlet series of $\varphi$. The permutation lemma itself is a special case of the general fact that a group acts on itself by left multiplication (Cayley's theorem in miniature), linking elementary number theory directly to abstract algebra.

Ask the tutor: How does the permutation property of reduced residue systems generalize to prove Euler's theorem for arbitrary finite abelian groups?

Picture the $n$ residue classes mod $n$ as $n$ equally spaced points on a circle, labeled $0, 1, \dots, n-1$. A complete residue system picks up every point once. Now shade the points that share a common factor with $n$: these are the "dead" points, useless for multiplicative inverses, because if $\gcd(a,n) = d > 1$ then $a$ can never be inverted mod $n$ (multiplying $a$ by anything lands only on multiples of $d$, never on $1$ unless $d=1$). The unshaded points are exactly the units — the reduced residue system lives on them. The second picture in your head should be multiplication as a symmetry of this unshaded set. Fix a unit $a$. Multiplying every unshaded point by $a$ (mod $n$) sends units to units — because a product of two units is again a unit — and it is injective on residues mod $n$ because $a$ is invertible. Since the unshaded set is finite, an injective self-map of it is a bijection: multiplying by $a$ just permutes the unshaded points among themselves. This single fact, visualized as "rotating/scrambling the dots without ever touching a shaded dot," is exactly what powers Euler's theorem later.

Example 1: $n = 18$. First compute $\varphi(18)$ directly from the definition: list $k = 1,\dots,18$ and keep those with $\gcd(k,18)=1$. Since $18 = 2 \cdot 3^2$, we discard multiples of $2$ or $3$:

are the survivors (check: $\gcd(1,18)=1$, $\gcd(5,18)=1$, $\gcd(7,18)=1$, $\gcd(11,18)=1$, $\gcd(13,18)=1$, $\gcd(17,18)=1$; all other residues $2,3,4,6,8,9,10,12,14,15,16$ share a factor of $2$ or $3$ with $18$). So

and $\{1,5,7,11,13,17\}$ is one RRS mod $18$. Now test the permutation property with $a = 7$ (note $\gcd(7,18)=1$). Compute $7 r_i \bmod 18$ for each $r_i$:

• $7 \cdot 1 = 7$
• $7 \cdot 5 = 35 \equiv 35 - 18 = 17 \pmod{18}$
• $7 \cdot 7 = 49 \equiv 49 - 36 = 13 \pmod{18}$
• $7 \cdot 11 = 77 \equiv 77 - 72 = 5 \pmod{18}$
• $7 \cdot 13 = 91 \equiv 91 - 90 = 1 \pmod{18}$
• $7 \cdot 17 = 119 \equiv 119 - 108 = 11 \pmod{18}$

The resulting residues $\{7, 17, 13, 5, 1, 11\}$ are exactly $\{1,5,7,11,13,17\}$ reordered — confirming the Theorem's part (B): multiplying an RRS by a unit permutes it. As a bonus check of the Corollary, $7^{\varphi(18)} = 7^6$ should be $\equiv 1 \pmod{18}$: indeed $7^2 = 49 \equiv 13$, $7^3 \equiv 7 \cdot 13 = 91 \equiv 1 \pmod{18}$, so $7^6 = (7^3)^2 \equiv 1^2 = 1 \pmod{18}$, matching Euler's theorem exactly.

Example 2: $n = 20$, an RRS not of the "standard" form. Here $20 = 2^2 \cdot 5$. The standard RRS from $\{1,\dots,20\}$ is $\{1,3,7,9,11,13,17,19\}$ (discard multiples of $2$ and $5$), so $\varphi(20) = 8$. To illustrate that any set of representatives, one per unit class, works — not just the least positive one — build a deliberately asymmetric RRS by shifting some representatives by multiples of $20$ and even using negative numbers:

Check each is coprime to $20$ and matches a distinct class among $1,3,7,9,11,13,17,19$:

• $1 \equiv 1$
• $-17 \equiv -17 + 20 = 3$
• $27 \equiv 27 - 20 = 7$
• $9 \equiv 9$
• $-9 \equiv -9 + 20 = 11$
• $33 \equiv 33 - 20 = 13$
• $-3 \equiv -3 + 20 = 17$
• $19 \equiv 19$

All eight target classes $\{1,3,7,9,11,13,17,19\}$ appear exactly once, and $\gcd$ of each listed integer with $20$ is $1$ (e.g. $\gcd(-17,20)=\gcd(17,20)=1$, $\gcd(27,20)=\gcd(7,20)=1$, $\gcd(33,20)=\gcd(13,20)=1$). So $T$ is a bona fide RRS mod $20$ with $|T| = 8 = \varphi(20)$, confirming part (A) even though $T$ looks nothing like $\{1,\dots,20\}$. Now apply the permutation property with $a = 9$ ($\gcd(9,20) = 1$) to the standard RRS $\{1,3,7,9,11,13,17,19\}$:

• $9\cdot 1 = 9$
• $9\cdot 3 = 27 \equiv 7$
• $9\cdot 7 = 63 \equiv 63-60=3$
• $9\cdot 9 = 81 \equiv 81-80=1$
• $9\cdot 11 = 99 \equiv 99-80=19$
• $9\cdot 13 = 117 \equiv 117-100=17$
• $9\cdot 17 = 153 \equiv 153-140=13$
• $9\cdot 19 = 171 \equiv 171-160=11$

The image set is $\{9,7,3,1,19,17,13,11\} = \{1,3,7,9,11,13,17,19\}$, confirming the permutation property once more, this time with an $a$ that is not itself in the RRS's "obvious" range in a special way (it's just a generic unit).