Back to the on-screen lesson ·
Counting the units modulo a number, why the count splits over the prime powers, and how badly it fails to grow with the number.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to compute Euler's totient from a factorisation, derive the prime-power formula by counting the multiples that are excluded, explain why the function is multiplicative over coprime factors by appeal to the Chinese remainder theorem, and say why the count is not monotone in the size of the number.
Lesson 7 said a residue has an inverse modulo $n$ exactly when it is coprime to $n$, and called those residues the units. Lesson 11 proved Fermat's theorem for a prime modulus, where every non-zero residue is a unit and there are $p - 1$ of them.
For a composite modulus the count is smaller and the theorem has to change to match. So the question this lesson answers — how many units are there modulo $n$ — is not a curiosity: it is the exponent that will appear in the generalisation of Fermat's theorem in the next lesson.
Euler's totient $\varphi(n)$ is the number of integers in $\{1, 2, \ldots, n\}$ that are coprime to $n$. By convention $\varphi(1) = 1$.
A reduced residue system modulo $n$ is a set of $\varphi(n)$ integers, one from each class of units — $\{1, 3, 5, 7\}$ modulo $8$, for instance. A complete residue system has $n$ elements, one per class; the reduced one keeps only the invertible classes.
$\varphi$ is multiplicative: $\varphi(mn) = \varphi(m)\varphi(n)$ whenever $\gcd(m, n) = 1$. It is not completely multiplicative — the coprimality is needed, and $\varphi(2 \cdot 2) \ne \varphi(2)^2$.
Prime powers first. Among $1, \ldots, p^{k}$ the numbers not coprime to $p^{k}$ are exactly the multiples of $p$, and there are $p^{k-1}$ of them. So $$\varphi(p^{k}) = p^{k} - p^{k-1} = p^{k}\left(1 - \tfrac1p\right).$$ In particular $\varphi(p) = p - 1$, which is what Fermat's theorem used.
Multiplicativity. If $\gcd(m, n) = 1$ then $\varphi(mn) = \varphi(m)\varphi(n)$. The reason is the Chinese remainder theorem: it matches residues modulo $mn$ with pairs of residues modulo $m$ and modulo $n$, and — because it is a ring isomorphism — it matches units with pairs of units. Counting both sides gives the identity.
The formula. Putting the two together, for $n = \prod p_i^{e_i}$, $$\varphi(n) = \prod_i \left(p_i^{e_i} - p_i^{e_i - 1}\right) = n \prod_{p \mid n}\left(1 - \frac1p\right),$$ the product running over the distinct primes dividing $n$. The exponents affect $n$ and not the proportion, so $\varphi(n)/n$ depends only on which primes divide $n$.
Two facts worth carrying. $\varphi(n)$ is even for every $n > 2$, because the units pair off as $a$ with $n - a$ and the two coincide only for tiny $n$. And $$\sum_{d \mid n} \varphi(d) = n,$$ which comes from sorting $1, \ldots, n$ by their gcd with $n$: those with gcd $d$ number $\varphi(n/d)$, and every residue lands in exactly one class.
How small can it be? Never below about $n/(e^{\gamma}\ln\ln n)$, so $\varphi(n)$ is always a substantial fraction of $n$ — which matters for RSA, where the private exponent is an inverse modulo $\varphi(n)$ and the search space must not be small.
Another way: steps
Another way: example
$\varphi(360)$, with $360 = 2^3 \cdot 3^2 \cdot 5$. Prime powers: $8 - 4 = 4$, $9 - 3 = 6$, $5 - 1 = 4$. Product $4 \cdot 6 \cdot 4 = 96$. By the other route: $360 \cdot \frac12 \cdot \frac23 \cdot \frac45 = 96$. Compare $\varphi(361) = \varphi(19^2) = 361 - 19 = 342$ — a much larger totient for a barely larger number, because $361$ has only one prime factor.
Multiplicativity is stated as a formula and it is really a statement about structure, and seeing it that way explains both why it is true and where it stops.
The Chinese remainder theorem gives a bijection $$\mathbb{Z}_{mn} \;\longrightarrow\; \mathbb{Z}_m \times \mathbb{Z}_n$$ for coprime $m$ and $n$, and it respects multiplication. A residue $x$ is a unit modulo $mn$ exactly when it has an inverse, and under a multiplication-respecting bijection that happens exactly when its image has one in each coordinate. So the units modulo $mn$ correspond precisely to pairs of units, one modulo $m$ and one modulo $n$. Counting: $\varphi(mn) = \varphi(m)\varphi(n)$.
Try it with $m = 3$, $n = 5$. The units modulo $15$ are $\{1, 2, 4, 7, 8, 11, 13, 14\}$ — eight of them. The units modulo $3$ are $\{1, 2\}$ and modulo $5$ are $\{1, 2, 3, 4\}$: two times four. And $7$, for instance, corresponds to the pair $(1, 2)$, both units.
Where it stops. For $m = n = 2$ the theorem does not apply, and indeed $\varphi(4) = 2$ while $\varphi(2)\varphi(2) = 1$. There is no bijection $\mathbb{Z}_4 \to \mathbb{Z}_2 \times \mathbb{Z}_2$ respecting multiplication; the two rings are genuinely different.
This is worth generalising in your head, because the same argument recurs. Any function counting something that splits across a product of coprime moduli is multiplicative, and $\tau$, $\sigma$ and $\varphi$ are the three standard examples. Once a function is known to be multiplicative, computing it anywhere reduces to computing it on prime powers, and that is usually a one-line count.
Multiplying without coprimality. $\varphi(12) = 4$, not $\varphi(2)\varphi(6) = 1 \cdot 2 = 2$. Split into prime powers, which are automatically coprime, rather than into any convenient factors.
Writing $\varphi(p^{2}) = (p-1)^{2}$. It is $p^{2} - p = p(p-1)$. Only the multiples of $p$ are excluded, and there are $p$ of them, not $2p - 1$.
Including the exponents in the product. $\varphi(n) = n\prod(1 - 1/p)$ runs over distinct primes. $\varphi(8) = 8 \cdot \frac12 = 4$, and the exponent $3$ appears only through the $8$.
Confusing it with the divisor count. $\tau(n)$ counts divisors, $\varphi(n)$ counts residues coprime to $n$. They pull in opposite directions: a number with many small prime factors has a large $\tau$ and a small $\varphi$.
Assuming $\varphi$ is increasing. It is not, and wildly so: $\varphi(30) = 8$ while $\varphi(31) = 30$. A prime has the largest possible totient for its size, and a product of small primes the smallest.
$\varphi(210)$, with $210 = 2 \cdot 3 \cdot 5 \cdot 7$: four distinct primes, so $210 \cdot \frac12 \cdot \frac23 \cdot \frac45 \cdot \frac67 = 48$.
Every small prime costs a large fraction.
$\varphi(211)$: $211$ is prime, so the answer is $210$.
A prime keeps everything but itself.
One more than a number with totient $48$ has totient $210$. The function is nowhere near monotone, and its value is a fact about the factorisation rather than about the size.
The contrast is the lesson.
For which $n$ is $\varphi(n) = 8$? Write $n = \prod p_i^{e_i}$; each prime power contributes $p^{e-1}(p-1)$, and the contributions multiply to $8$.
A constraint on the factorisation.
So each $p - 1$ divides $8$, giving $p \in \{2, 3, 5\}$, and the possible prime-power contributions are $\varphi(2)=1$, $\varphi(4)=2$, $\varphi(8)=4$, $\varphi(16)=8$, $\varphi(3)=2$, $\varphi(9)=6$, $\varphi(5)=4$.
A short list, because $p-1$ is heavily constrained.
Combining coprime powers to a product of $8$ gives $n \in \{16, 20, 24, 30\}$ — a finite list, as it always is: only finitely many $n$ have any given totient.
Finiteness is what makes the question answerable at all.
Pair each unit $a$ with $n - a$, which is also a unit since $\gcd(n - a, n) = \gcd(a, n) = 1$.
The pairing is the whole argument.
The pair collapses only when $a = n - a$, that is $n = 2a$ — and then $a = n/2$ shares the factor $a$ with $n$ unless $a = 1$, so for $n > 2$ no unit is paired with itself.
The exceptional case is the one to examine.
So the units fall into disjoint pairs and there is an even number of them.
Match each number to how many residues below it are coprime to it.
| $32$ | $24$ | $12$ | |
|---|---|---|---|
| $120$ | |||
| $35$ | |||
| $21$ |
How many of $1, 2, \ldots, 70$ are coprime to $70$?
Answer:
Give the totient of each number.
| Totient | |
|---|---|
| $9$ | |
| $24$ | |
| $28$ |
Is this true: $\varphi(n)$ counts the divisors of $n$?
For the prime $43$, give $\varphi(43)$ and $\varphi(1849)$.
totient of the prime a, totient of its square c
The divisors of $253$ are $1$, $11$, $23$ and $253$. Give the totient of each.
| Totient | |
|---|---|
| $1$ | |
| $11$ | |
| $23$ | |
| $253$ |
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Match each number to how many residues below it are coprime to it.
| $24$ | $12$ | $6$ | |
|---|---|---|---|
| $45$ | |||
| $28$ | |||
| $14$ |
You can compute how many residues below a number are coprime to it, from the factorisation alone. Say in your own words why the exponents in the factorisation do not affect the proportion of residues that survive. Next: what that count is the right exponent for.
9. Your turn: show that $\varphi(n)$ is even for every $n > 2$, step 3