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

Question

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.

Answer 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!

Answer 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.

Answer 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.

Answer 4

You can also begin by anouncing Euler's Theorem $$(a\wedge n)=1 \;\; \implies a^{\phi(n)}\equiv 1 \; \mod n$$ or

$$a^{\phi(n)+1} \;\equiv a \mod n$$ and explain that we can use this in cryptography. For this you can take a simple example to explain the RSA system. The students will be motivated to understand how it works.

Answer 5

You could introduce it as the number of natural numbers ( non-zero) less than $n$ such that their lcm with $n$ is their product. Of course, it's the number of irreducible fractions in the closed interval [0,1] with denominator $n$. It's an upper bound in a range of $n$ integers on the number of primes (except the first n).Its square is therefore a very weak approximation on the number of Goldbach partitions of even numbers less than $2n$. etc.

Answer 6

The Euler's $φ$ function provides a generalization of Fermat's little theorem.

Fermat: $x^{n-1} ≡ 1 \pmod{n}$ for any prime $n$ and integer $x$ such that $\gcd(x,n) = 1$.

Euler: $x^{φ(n)} ≡ 1 \pmod{n}$ for any positive integer $n$ and integer $x$ such that $\gcd(x,n) = 1$.

In mathematics we are always interested in generalizations, especially if the generalization tells us more about the structures we are interested in. Here it is about the structure of the ring of integers modulo $n$. So Fermat's little theorem naturally motivates Euler's theorem.

Contrary to the erroneous claim by another answerer that Euler's theorem is needed to prove the correctness of RSA, Fermat's little theorem suffices. I will now give such a proof.

We wish to prove that $m^{c(p-1)(q-1)+1} ≡ m \pmod {pq}$ for distinct primes $p,q$ and natural $c$, so that for any naturals $m,k,d$ such that $kd ≡ 1 \pmod{(p-1)(q-1)}$, we can from $m^k$ and $d$ compute $(m^k)^d ≡ m \pmod{pq}$. The proof is very easy via Fermat's little theorem: If $p \mid m$ then trivially $m^{c(p-1)(q-1)+1} ≡ 0 ≡ m \pmod {p}$. If $p \nmid m$ then $m^{c(p-1)(q-1)+1} ≡ (m^{c(q-1)})^{p-1}·m ≡ m \pmod {p}$ since $p \nmid m^{c(q-1)}$. In either case $p \mid m^{c(p-1)(q-1)+1} - m$ and by symmetry $q \mid m^{c(p-1)(q-1)+1} - m$ as well, therefore $pq \mid m^{c(p-1)(q-1)+1} - m$ since $p,q$ are distinct. Done.

There are also many properties of the $φ$ function that are of mathematical interest, such as the fact that if there is a primitive root modulo $n$ then there are $φ(φ(n))$ of them modulo $n$. This question can arise naturally when we know (as Euler proved) that there is a primitive root modulo every prime $p$. In particular, there are $φ(p-1)$ primitive roots modulo any given prime $p$, and so the $φ$ function provides the most elegant way to count this number of primitive roots.

Answer 7

Here is a way of explaining it to students who have no background in mathematics other than counting.

Let me explain with an example. Take any number say $a = 20$ and any number less than it say $b = 15$. We can divide $20$ into equal parts in many ways such that each part is $>1$ e.g.

$$ 20 = 10 + 10 = 4 + 4 + 4 + 4 + 4 = \color{red}{5 + 5 + 5 + 5} = 2 + 2 + \cdots+ 2 $$

Similarly can divide $15$ into equal parts in many ways such that each part is $>1$ e.g.

$$ 15 = 10 + 10 = 3 + 3 + 3 +3 = \color{red}{5 + 5 + 5} $$

What we observe is that there is a partition of the smaller number $15 = \color{red}{5+5+5}$ which appears as a sub-string in the partition of the larger number $20 = \color{red}{5+5+5+5+5}$.

For how many numbers less than $20$ can we find such a sub-string and for how many numbers can we can we never find a sub-sting e.g. the number $b = 9$.

Thus Euler's Phi function $\varphi(n)$ is the number of natural numbers less than $n$ for which we cannot find an equi partition which is a sub string of $n$.