Modular arithmetic – Beyond the Definitions

Modular arithmetic is a relatively simple idea to define. The natural motivation is to consider a clock. The display of a standard analogue clock makes no distinction between 4am, 4pm, and 4pm next Thursday. This is a direct visualisation of the integers modulo 12. Instead of counting in the usual way, where each successive integer is different to all those considered previously, here, every time we get to a multiple of 12, we reset our count back to zero. As a result, this procedure is often referred to as `clock arithmetic’.

A common problem for good students, for example those starting the UKMT’s Senior Mentoring Scheme, is that the idea of modular arithmetic seems very simple, but it’s hard to work out how it might be useful in application to problems. My claim is that the language of modular arithmetic is often the best way to discuss divisibility properties in problems about whole numbers. In particular, the behaviour of powers (ie and so forth) is nice in this context, and the notation of modular arithmetic is the only sensible way to approach it. Anyway, let’s begin with a quick review of the definitions.

Definitions

We are interested in divisibility by some fixed integer , and the remainders given after we divide by n. Given an integer M, we can write this as:

and this decomposition is unique. We then say that M is congruent to a modulo n. Note that working modulo n, means that we are interested in remainders after division by n (rather than a or k or M or anything else). This has the feeling of a function or algorithm applied to M. We get told what M is, then work out the remainder after division by n, and say that this is `M mod n‘.

This is fine, but it very much worth bearing in mind a slightly different interpretation. Working modulo n is a way of saying that we aren’t interested in the exact value of an integer, only where it lies on the n-clock. In particular, this means we are viewing lots of integers as the same. The `sameness’ is actually more important in lots of arguments than the position on the n-clock.

More formally, we say that or a is congruent to b modulo n, if they have the same remainder after division by n. Another way of writing this is that

Sets of integers which are equivalent are called congruence classes. For example is a congruence class modulo 3. Note that under the first definition, we consider all elements here to be congruent to 2, but in a particular question it may be more useful to consider elements congruent to -1, or some combination.

These definitions are equivalent, but it can be more useful to apply this second definition for proving things, rather than writing out or whatever all the time.

Addition and Multiplication

Everything has been set up in terms of addition, so it is easy to see that addition works well on congruence classes. That is:

We could argue via a clock argument, but the second definition works very well here:

We want to show that a similar result happens for multiplication. But this holds as well:

Let’s just recap what this means. If we want to know what is modulo 9, it suffices to say that and , and so . In a more abstract setting, hopefully the following makes sense:

This is exactly the statement of the result in the case n=2, where the congruence classes are the odd integers and the even integers.

Powers

What happens if we try to extend to powers? Is it the case that

Unfortunately not. If we work modulo 3, then , but . However, we can still get some interesting results. Consider the powers of 2 modulo 7:

We see that it cycles through 1, 2, 4. The fact that it cycles is unsurprising once we know that it eventually gets back to 1. By the multiplication property above, for example

So in fact, the value of modulo 7 is dependent precisely on the value of n modulo 3. Considering powers modulo primes and then modulo composite numbers throws up a whole range of interesting theory, in particular Fermat’s Little Theorem, which states that modulo a prime p:

This implies that for all a. Considering small cases of this theorem, and attempting a general proof is an excellent exercise in the theory, and so I will say no more about it here.

Division

Perhaps the most confusing thing about working modulo n is the question: can I do division? The first thing to consider is: what does division actually mean? We are so comfortable with dividing integers and general real numbers that it is easy to forget that the most natural definition of division by m is: `the inverse of multiplication by m‘. This is what we need to keep in mind to make a sensible definition of division in this context.

Let’s begin with an example. Suppose we want to work out modulo 7. Then x satisfies the modular equation . There are only 7 possible values of x (modulo 7 of course) to check, and we see that only one of them, 4 in this case, satisfies the equation. So we say that .

The key was that precisely one congruence satisfied the equation. Proving that this will work in general is a little bit tricky. In fact, it is not true in some cases. For example, let’s work with a composite modulo base, say , and let’s try to divide by 2. Then

In fact this is the only kind of situation where it will go wrong. If we try to divide by an integer which is coprime to the modulo base, then we always get a unique answer. So in the case where the modulo base is a prime p, then we can divide by anything except p itself. To prove all of this in general, it is probably is easiest to use the Euclidean algorithm. This is undoubtedly something worth thinking about.

As a final remark, we can combine this and the discussion of powers to show that some positive power is eventually congruent to 1, and so we do indeed have a cycle. We work modulo n, and assume that we are looking at where a and n are coprime. Then, because can only take finitely many values modulo n, there must be two the same.

Further things

Here are a couple of things to think about once all of that has been digested.

• It is a well-known and useful result that an integer is divisible by 3 if and only if the sum of its digits is divisible by 3. This is something that everyone should have a go at proving themselves. I will however mention that we get from sums of digits to the number itself by multiplying each digit by some power of 10 and then adding and we have established that modulo arithmetic preserves useful properties under these operations.
• We might notice that no perfect square is congruent to 3 modulo 4. This observation opens up the more general consideration of quadratic residues, that is: which congruences classes appear as perfect squares modulo n? The answers turn out to be elegant but perhaps more complicated than one might suspect. The question of whether -1 is a perfect square modulo n is of particular interest.
• If you know what a group is, you will observe that addition modulo n is an abelian group, with the congruence classes as elements. Unsurprisingly, this is isomorphic to . More interestingly, multiplication on the classes coprime to n is also an abelian group, though its properties are less obvious. For many of the results we might want, including an extension of Fermat’s Little Theorem to composite bases, this is very much the right way to think about modular arithmetic. Conversely, you could say that this is one of the best examples of a group, and perhaps is easier to think about than the symmetries of a dodecahedron and other canonical examples.

This is now available as a pdf here.

Advertisement