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 m^n 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 n\geq 2, and the remainders given after we divide by n. Given an integer M, we can write this as:

M=kn+a,\quad\text{ where }a=0,1,\ldots,n-1,

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 a\equiv b 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

a\equiv b\quad \iff \quad n|a-b.

Sets of integers which are equivalent are called congruence classes. For example \{\ldots,-4,-1,2,5,8,\ldots\} 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 b=kn+a 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:

\text{If }a\equiv b,c\equiv d,\quad\text{then }a+c\equiv b+d.

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

\text{We have }n|a-b,n|c-d,\quad\text{and so }n|(a+c)-(b+d),\text{ exactly as required.}

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

\text{If }a\equiv b,c\equiv d,\quad\text{then }n|c(b-a)\text{ and }n|b(c-d).

\Rightarrow n|ac-bd,\text{ that is }ac\equiv bd.

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

\text{ODD}\times\text{ODD}=\text{ODD};\quad \text{EVEN}\times\text{EVEN}=\text{EVEN};\quad \text{ODD}\times\text{EVEN}=\text{EVEN}.

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

\text{if }a\equiv b,c\equiv d,\quad\text{then }a^c\equiv b^d?

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

2^0\equiv 1,\quad 2^1\equiv 2\quad, 2^2\equiv 4,\quad 2^3\equiv 1,\quad 2^4\equiv 2,\quad 2^5\equiv 4,\quad 2^6\equiv 1,\ldots

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

2^7\equiv 2^3\times 2^3\times 2\equiv 1\times 1\times 2\equiv 2.

So in fact, the value of 2^n 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:

a^{p-1}\equiv 1\mod p\quad\text{whenever }p\not|a.

This implies that a^p\equiv a 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 x\equiv1\div 2 modulo 7. Then x satisfies the modular equation 2x\equiv 1. 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 4\equiv1\div 2.

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 6=2\times 3, and let’s try to divide by 2. Then

2x\equiv 0\text{ has two solutions (0 and 3),}\quad 2x\equiv 1\text{ has no solutions, all modulo 6.}

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 a^m where a and n are coprime. Then, because a^m can only take finitely many values modulo n, there must be two the same.

\text{Say }a^r\equiv a^s, r>s\quad\Rightarrow\quad a^{r-s}=a^r\div a^s\equiv 1,\text{ as desired.}

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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s