What is a good way to introduce Euler's totient function?

I was thinking of this question and when I googled I couldn't find any MSE results, but I found one from Reddit. I just wanted to ask the question here and post the answer as community wiki just so MSE could have some discussion. If you want this taken down, you can comment and I'll take it down.

The question from u/matqkks:

I need to introduce Euler's totient function but I don't want to start with the definition. What applications and impact does this function have? I need something which will can be used to hook students into why Euler's totient function is important.

If you have other ideas for good ways to teach this function, please add your answer!

Edit: another good tactic is if someone knows of some problem (that's natural enough to formulate) where we do stumble across the totient function early on, but in fact the problem is so "deep" that even though its "purpose" is to introduce the totient function (in terms of why/how a mathematician would come up with such a definition), it's also a good springboard into harder number theory questions, kind of like in this thread: Simple theorems that are instances of deep mathematics.

Solution 1:

The answer from u/lurking_quietly:

What makes Euler's totient function important is that for all positive $n\geq 2$, $\varphi(n)$ counts the number of elements of $\mathbb Z/n\mathbb Z$ which admit multiplicative inverses (i.e., $\varphi(n)$ counts the number of distinct units in this ring.)

Rather than have your students compute $\varphi(n)$ with no motivation, you might first ask them to compute the size of the unit group, $|U(\mathbb Z/n\mathbb Z)|$ for various values of $n\geq2$. When you later define the totient function via $\varphi(1) := 1$ and

$$\varphi(n) := |\{ k : 1≤k≤n \text{ and } \gcd(k,n) = 1 \}|,$$

then your students might better appreciate that you're computing something with relevance by introducing this definition of the totient function. (Note: $n=1$ merits emphasis as a special case. The definition above does indeed recover $\varphi(1)=1$, as desired. But in general, the "correct" definition of the totient function would be $\varphi(n) = |U(\mathbb Z/n\mathbb Z)|$. For the case $n=1$, this might be potentially ambiguous if we require $0\neq 1$ in the quotient ring, something very common in the definition of fields, for example.)

$$\rule{100pt}{1pt}$$

You can also introduce the totient function in the context of something like the finite sequence

$$\frac 1n, \frac 2n, ..., \frac{n-1}{n}, \frac nn.$$

For a fixed positive integer $n\geq 2$, how many elements for this sequence of order n have denominator $k$ when the fraction $j/n$ expressed in lowest terms? Answer: if $k|n, \varphi(k)$; otherwise, zero. This is related to the divisor sum identity given on the Wikipedia page for the totient function. There are multiple ways to verify this, ranging from the direct to Möbius inversion.

There are other directions you can go, too. For example, if your students are familiar with a little bit of ring theory, then you can explore how not only is $\varphi$ a multiplicative function, but its multiplicativity is closely related to the Chinese Remainder Theorem over the integers. If $m, n$ are positive integers greater than $1$ and $\gcd(m,n)=1$, then not only do we have

$$\varphi(mn) = \varphi(m) \varphi(n),$$

but we have the stronger result that

$$\mathbb Z/mn\mathbb Z \cong \mathbb Z/m\mathbb Z × \mathbb Z/n\mathbb Z$$

which restricts to an isomorphism of the unit groups of the respective rings:

$$U(\mathbb Z/mn\mathbb Z) \cong U(\mathbb Z/m\mathbb Z) × U(\mathbb Z/n\mathbb Z).$$

Roughly speaking, this means that when $m, n$ are coprime, not only is the number of units modulo $mn$ the same as (the number of units modulo $m$)$\times$(the number of units modulo $n$), but we also have that a unit modulo $mn$ is expressible in a unique way as the product of a unit modulo $m$ and a unit modulo $n$.

If you're even more ambitious (and have enough time), you might even consider possible generalizations to the totient function, too. For example, what might something like "$\varphi(1+4i)$" mean? One natural idea would be to try to count the number of units $|U(\mathbb Z[i]/(1+4i)\mathbb Z[i]|$, or the number of units in the Gaussian integers modulo $1+4i$. Or, alternatively, say that $p$ is a positive integral prime, and consider the polynomial ring $\mathbb Z/p\mathbb Z[x]$. What might "$\varphi(p(x))$" mean in context? Suggestion: set $(p(x)) := |U(\mathbb Z/p\mathbb Z[x]/(p(x))|$, the size of the group of units for polynomials in one variable with coefficients in $\mathbb Z/p\mathbb Z$, all modulo the polynomial $p(x)$.

I hope something in the above proves useful. Good luck!

Solution 2:

There can be no one right answer to this question. If you are looking for an approach requiring only knowledge of divisors and addition, I propose the following idea. Given an function defined on integers $\,a(n)\,$ we can compute the sum of this function over the divisors of $\,n\,$ by defining $$ b(n) := \sum_{d|n} a(d). \tag{1}$$ If $\, a(n) = 1\,$ then $\, b(n) = \tau(n).\,$ If $\, a(n) = n\,$ then $\, b(n) = \sigma(n).\,$ There are other simple examples of this kind you can try out.

By reversing the process, given a function $\,b(n)\,$ we can ask how to find a function $\,a(n)\,$ that will produce it given equation $(1)$. Using $\,b(n) = 1\,$ produces a trivial solution for $\,a(n).\,$ The next case to try is when $\,b(n) = n \,$ as in the equation $$ \sum_{d|n} a(d) = n. \tag{2}$$ The unique solution is the Euler totient. It is easy to solve the first few equations $$ a(1)\!=\!1, a(1)\!+\!a(2)\!=2, a(1)\!+\!a(3)\!=\!3, a(1) \!+\!a(2)\!+\!a(4)\!=\!4$$ and determine the unique solution $$ a(1)=1,\; a(2)=1,\; a(3)=2,\; a(4)=2 $$ and now propose some simple conjectures of what its values are in general.

Other applications and properties can be introduced later. There is much information about properties and applications in the OEIS sequence A000010 entry for the Euler totient and the references contained there.

Solution 3:

There are many practical implications for $\phi(n)$. Suppose you have $n$ players arranged in a circle. Each time a player takes a turn, play skips to $k$th next player. For how many $k$ will everyone get a turn? You can also ask how many fractions there are with denominator $n$, if you require the number to be between $01$ and $1$ (exclusive), and the fraction to be in simplified form.