Modular Arithmetic!

Cardiac Linfarction's excellent post about RSA assumed some knowledge of modular arithmetic. This is not a term that most people encounter in their lives, I would wager, so let me explain it to you right quick. I've attempted to organize the post so that you can stop reading whenever it gets too meaningless for you and come away with at least some understanding of what "mod" means.

The phrase "A modulo B," where A and B are positive (for now) whole numbers, is often shortened to "A mod B," and it means "the remainder you get when you divide A by B." For example, 7 mod 3 is 1.

There are a lot of numbers that are (e.g.) 1 modulo 3. 7 is one of them, as are 4, 10, 13, 16 - any number of the form 1 + 3k, where k is some positive integer. Similarly, the numbers 2, 5, 8, 11, ... (all = 2 + 3k for some k) give you a remainder of 2 when divided by 3 and hence are 2 mod 3, and all the multiples of 3 are 0 mod 3. Since these are all the remainders one could possibly get, the modulus 3 splits the integers into three classes: 0 mod 3, 1 mod 3, and 2 mod 3. These are called residue (or congruence, or equivalence) classes, and two members of the same class are called equivalent (or congruent) modulo 3 (or modulo B in general). All those pictures in Cardiac Linfarction's post with the "triple equals sign?" That symbol means "is equivalent to."

As you might have guessed from the title of the post, we can add and multiply these residue classes together. Consider A mod B and C mod B - remember, "A mod B" represents the entire class of numbers that are A modulo B. Pick any representative of each class; these can be written A + Bm (heh, BM) and C + Bn for integers m, n. Now notice that the sum of these two numbers is A + C + B(m+n), which when reduced modulo B is just A + C, a representative of the residue class A + C mod B. So: (A mod B) + (C mod B) = A + C mod B, just like you'd hope. It's also true that (A mod B)*(C mod B) = AC mod B. For example, 7 mod 5 + 11 mod 5 = 18 mod 5 = 3 mod 5 (alternatively: 7 mod 5 + 11 mod 5 = 2 mod 5 + 1 mod 5 = 3 mod 5, i.e., it doesn't matter at which step you actually compute the modulus).

The clock is a good example of arithmetic modulo 12, where the 12 on the clock acts like 0, in the sense that, for example, 3 o'clock + 12 hours = 3 o'clock. We also have, say, 7 o'clock + 6 hours = 1 o'clock, noting that 7 + 6 mod 12 = 13 mod 12 = 1.

See? Modular arithmetic is not that hard, and you use it every day.

Let's prove a cool fact using modular arithmetic: Any perfect square (e.g. 1, 4 = 2^2, 9 = 3^2, 16 = 4^2, ...) is either 0 or 1 mod 4 (i.e., cannot be 2 or 3 mod 4).

Let n be any integer; then n is either 0, 1, 2 or 3 mod 4 (those are all the possible remainders when dividing by 4). If n mod 4 = 0 mod 4, then n^2 mod 4 = 0^2 mod 4 = 0 mod 4. Similarly, if n mod 4 = 1 mod 4, then n^2 mod 4 = 1 mod 4. Now if n mod 4 = 2 mod 4, then n^2 mod 4 = 2^2 mod 4 = 4 mod 4 = 0 mod 4! Similarly, if n mod 4 = 3 mod 4, then n^2 mod 4 = 9 mod 4 = 1 mod 4. QED.

There are a shitload of questions you can ask about residue classes, and they get pretty hard pretty fast. It's easy to prove what we just proved, that the polynomial n^2 always produces values that are either 0 or 1 mod 4; can we say anything about a general polynomial f(n) to a general modulus? How are the primes distributed among residue classes modulo N, for N some positive number? What if the modulus N itself is a function of some parameter x - how are the primes up to x distributed modulo N(x)? (This is known for some functions of x, but in general it is a very, very difficult open problem.)

CL also talks about Euler's totient function, phi(n). phi(n), as CL explained, is the number of residue classes whose least positive element is coprime to n (i.e., there are no primes that divide both n and the element from the residue class). Why do we care about these particular residue classes?

What distinguishes the coprime residue classes is that they are invertible - that is, if A mod N is a coprime residue class (so if A is the smallest positive member of the class then A is coprime to N), then there exists another (coprime) residue class B mod N such that (A mod N)(B mod N) = A*B mod N = 1 mod N. So we can multiply A mod N by something to get 1 mod N. If A is not coprime to N, then it is impossible for A mod N to be invertible (trust me, or prove it yourself!).

The punchline: If N is a prime number, then every integer smaller than N is coprime to N (indeed, primes have no divisors besides themselves and 1). So the collection of residue classes modulo N form a collection of objects that you can add, subtract, multiply and divide. There is an element that acts like zero (does nothing when adding, and anything times it is zero), and an element that acts like one (it * (whatever) = whatever). All of this is also true for the integers, and these arithmetic operations yield a beautiful, subtle and not-totally-understood-at-all underlying structure (i.e. the distribution of primes, which is partially understood, for just one example) - so by virtue of the presence and "wholeness" (in some sense) of these operations for the integers modulo a prime, a similar structure must be present.

What is this structure? You might want to start here.

Anyway. This was fun. Modular arithmetic is pretty simple on its face, and it's also a massively powerful tool in number theory. In particular, it comes up a lot in talking about RSA.