The Power of an Example – Modular Mathematics

Recently I took a class of students on a Physics excursion. On the trip there, I observed some of them working a Maths C assignment on modular multiplication. I knew a bit of mod mathematics from my programming experience, and was able to help them on some of the tougher concepts, but something a student said, instantly cleared up some aspects of Group Theory that I had been struggling with for years.

Firstly, some preliminary concepts. Modular mathematics is a conceptual extension (and a numerical restriction) of normal Integer addition and multiplication. All the normal rules of adding and multiplying Integers still apply, but once you get an answer larger than a certain number (called your modulus, let's say 12), you subtract your modulus (12) until you end up with a remainder that is smaller. (If we have a negative number, we add 12's until we end up with something positive).
We then say that we have our answer, mod 12.
Here's some examples:

$ 4 + 9 = 13 = 1 \text{ mod }12 $

$ 8 \times 7 = 56 = 56 – 4 \times 12 = 8 \text{ mod } 12 $

So we've conceptually added an extra step onto addition and multiplication, that practically restricts our answers to Integers between 0 and 11.
Another name for this type of mathematics is “Clock Mathematics”, because on an analogue clock, if you treat the 12 as a 0, once you go past 12 noon or midnight, you start over at 0 o'clock.

The cool thing is that we can have additive and multiplicative inverses (think subtraction and division) in this system, that are also Integers. Once you've limited yourself to numbers less than 12 (or 8 or 7 or whatever number you decide to mod by), you no longer need fractions or negative numbers to do subtraction or division.

Additive Inverse (Modulo 10)

$ 8 + a = 0 \text{ mod } 10 $

$ a = -8 \text { mod } 10 $

$ a = -8 + 10 \text{ mod } 10 $

$ a = 2 \text{ mod } 10 $

$ 8 + 2 = 10 = 0 \text{ mod } 10 $

Multiplicative Inverse (Modulo 10)

$ 3 \times a = 1 \text{ mod } 10 $

$ 3 \times a = 10 + 10 + 1 \text{ mod } 10 $

$ 3 \times a = 21 \text{ mod } 10 $

$ a = 21/3 \text{ mod } 10 $

$ a = 7 $

$ 3 \times 7 = 21 = 1 \text{ mod } 10 $

Back to the story. My students were calculating the multiplicative inverses of the Integers, modulo 10, and one student pointed out that you could ignore multiples of 2, because there was no way you could multiply an even number by anything, divide by 10 and get a remainder of 1. Effectively you were looking for a multiple of two that was odd.
I realised that this also applied to multiples of 5. Since anything multiplied by 5 mod 10 would give you either 5 or 0, 5 didn't have an inverse in this case.

And that made Euler's totient function a hell of a lot clearer.