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 $

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

__. Effectively you were looking for a multiple of two that was__

**remainder of 1**__.__

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

## No comments:

## Post a Comment