Discrete Math - Day 27

Today we finished looking at the Euler totient function φ(n). There were about a half-dozen students who were out for the previous class, so I had students at their tables go over φ(n) with the missing students. This was an opportunity to catch up people while reinforcing the learning from yesterday.

The next facet of φ(n) to look at was summing the φ(k) for all divisors, k, of n. As an example, if n=15, the divisors of 15 are 1, 3, 5, and 15. Calculate the following: φ(1) + φ(3) + φ(5) + φ(15). It turns out this sum just equals 15, i.e.

     n = φ(1) + φ(2) + ... + φ(n)

I asked students if this would always be true and why. It was interesting to see the approaches different students took. Some students proceeded to calculate the values for more integers and verify that it was working. Some looked at relationships with prime numbers versus composite numbers.

One student asked why we should care if it is always true and that we could worry about it not working when we encountered that situation. I countered with the idea that we want to distinguish between some interesting curiosity versus something that we know is always true and can be built upon. If we don't know that a statement is always true it is just a curiosity. What we are trying to do in this is understand the mathematics that underlies relationships that we see so we can better understand what is happening and why.

The class discussion that followed actually proved to be quite productive on one front. One group had focused on the result for prime numbers. As a result the informally proved that φ(n) = φ(n) + φ(1) when n is prime. This result comes immediately from the fact that φ(1) = 1 and the number of integers less than a prime number p that are relatively prime to p is p - 1. Therefore for any prime, p, we have φ(p) = p - 1 and, therefore, φ(n) = φ(n) + φ(1) when n is prime.

This was an exciting result, at least from the teacher's perspective. It provided a proof for a specific case of the identity we were exploring. The result for composite numbers was not as forthcoming. Students were trying to make a connection between the divisors and relative prime numbers but that's about as far as it went.

We next looked at distinct prime divisors, d_i, of an integer n and calculated n(1 - 1/d₁)(1 - 1/d₂)...(1 - 1/d_m). For example for n=15 we calculate 15(1 - 1/3)(1 - 1/5). It turns out that n(1 - 1/d₁)(1 - 1/d₂)...(1 - 1/d_m) = φ(n). Several students noticed this connection and others were surprised.

We concluded with a brief discussion that this relationship and the previous relationship were connected. I also revisited that idea that φ(2n) = n. Class time did not allow further pursuit of all of these other than the results are all connected.

Students wrote a brief summary in their notes about connections they saw between prime numbers and relatively primes.


Visit the class summary for a student's perspective and to view the lesson slides.