Modular Arithmetic

Jason Rosenhouse’s post about numbers mentions that he’s not touching modular arithmetic, so I suppose I should talk about that instead. Modular arithmetic is simply the arithmetic of remainders. In elementary or middle school, everyone learns that an odd number plus an odd number is an even number, an even plus an odd is odd, an odd times an even is even, and so on.

The arithmetic of odds and evens is simply arithmetic modulo 2, since we’re only concerned with whether an integer leaves a remainder of 0 or 1 when divided by 2. The three statements in the previous paragraph translate, in order, to 1 + 1 = 0 mod 2, 0 + 1 = 1 mod 2, and 0*1 = 0 mod 2. The mod operator is a shorthand for “modulo,” and pronounced either “modulo” or “mod”: “one plus one equals zero mod two.”

The same trick applies to any other integer. If a and b are any two integers, then the remainder a + b leaves when divided by 3 – or, in more technical language, the residue class of a + b mod 3 – only depends on the residue classes of a and b mod 3. To use random numbers as illustration, 2 + 8 = 10 is in the same residue class mod 3 as 5 + 2 = 7.

There’s one modular arithmetic everyone’s familiar with – arithmetic modulo 12, or sometimes 24. Four hours after ten o’clock is always two o’clock, regardless of whether it’s in the a.m. of 2006/2/1 or the p.m. of 2006/2/14. Likewise, 10 + 4 always equals 2 mod 12.

So we can add residue classes mod any integer n. We can also subtract, using the same principle. We can multiply, although multiplication sometimes acquires strange properties. For example, 2*3 = 0 mod 6, whereas in normal arithmetic, the product of two nonzero integers is always nonzero.

Division is somewhat trickier, though. Modular arithmetic is only defined for integers, not for rational numbers. It’s easy to tell that 17 = 7 mod 10, but what is 1/2 mod 10?

With normal integers, we can always form rational numbers. This is because for every nonzero integer a, there’s a rational number 1/a, with the property that a/a = 1. Then the fraction b/a = b*(1/a). So you may ask, is it even defined in modular arithmetic?

It turns out it is, sometimes. For a concrete example, let’s work mod 10. We have 3*7 = 21 = 1 mod 10, so we can define 1/3 to be 7, and 1/7 to be 3. In more technical language, 7 is the inverse of 3 and vice versa. Then division by 3 is essentially the same as multiplication by 7.

However, there exists no n such that 2*n = 1 mod 10. To see why, let’s work mod 2 instead of mod 10. We can do that because 2*5 = 10, so we can just let 1, 3, 5, 7, and 9 mod 10 be 1 mod 2, and 0, 2, 4, 6, and 8 mod 10 be 0 mod 2. We need to have 0*n = 1 mod 2, then. But that’s impossible, because 0*0 = 0*1 = 0 mod 2.

This holds for every integer other than 1 that either divides 10, or has a common factor with 10 greater than 1; the trick is to look at residue classes mod that number. Fortunately, it holds for all other integers. The numbers 2, 4, 5, 6, and 8, and of course 0, have the factors 2 or 5 in common with 10. For the others, we have 1*1 = 3*7 = 9*9 = 1 mod 10.

Not coincidentally, the best numbers to do modular arithmetic with are the prime numbers. If we work mod p, then since the only factors of p are itself and 1, the only common factor greater than 1 that n can have with p is p. But if n is divisible by p, then it must be 0 mod p. Therefore, all residue classes mod p except 0 have inverses.

Now, you may ask why anyone cares about modular arithmetic. The answer is, first, it’s important in computing. Much of computer science works mod 2, since gates only have two states – false, corresponding to 0, and true, corresponding to 1.

Second, in pure math, it’s very useful to use modular arithmetic since there’s a finite number of residue classes mod every n. My favorite example here is the equation a^2 – 7b^2 = 3. There are many solutions to the equation, like a = SQRT(3) and b = 0. But there are no solutions where both a and b are integers.

We can’t verify that with every possible pair of integers, since there are infinitely many integers. But we can verify that using modular arithmetic. If there’s a solution in integers, then there’s also a solution modulo every n. For example, let’s pick n = 7. The equation then becomes a^2 = 3 mod 7, since 7b^2 is obviously 0 mod 7.

Now that the equation is in modular arithmetic, we can just plug in every residue class mod 7 to see if it works. If a = 0 mod 7, then a^2 = 0 mod 7. If a = 1 mod 7, then a^2 = 1 mod 7. If a = 2, 3, 4, 5, 6 mod 7, then a^2 = 4, 2, 2, 4, 1 mod 7. In none of the cases is a^2 equal to 3 mod 7, so we can conclude that the equation has no solutions in integers.