Introduction to Modular Arithmetic, Part 1

See all posts in this series

I have mentioned modular arithmetic (sometimes known as "clock arithmetic") in several of my posts. But this may not be helpful if you haven't come across this type of arithmetic before.

The idea of arithmetic modulo \(k\) (where \(k\) is some positive integer) is that, instead of checking whether two numbers \(m\) and \(n\) are equal, you just ask whether \(m\) and \(n\) leave the same remainder when you divide them by \(k\). If so we say that they are congruent modulo \(k\) (or mod \(k\)), and we write

\(m \equiv n~~(\mathrm{mod}~k)\,.\)

(Notation varies a bit between authors here.)

For example,

\(237 \equiv 1397 ~~(\mathrm{mod}~10)\),

because they both leave remainder \(7\) when you divide by \(10\).

More generally, for positive integers \(m\) and \(n\), \(m\) is congruent to \(n\) modulo \(10\) if and only if \(m\) and \(n\) have the same final decimal digit.

When we work modulo \(10\), there are \(10\) possible remainders (\(0,1,\dots,9\)).

Of course we don't have to work modulo \(10\). If we work modulo \(2\) there are only two possible remainders, \(0\) or \(1\), corresponding to whether your integer is even or odd.

What do we do about negative integers and zero? Well, we have to agree what we mean by the remainder in this case. What is the remainder when you divide \(-14\) by \(10\)? You might think the answer should be \(-4\). However we want our remainder to be in \(\{0,1,\dots,9\}\), so we have to write

\(-14 = (-2)\times 10 + 6\)

so that the remainder is \(6\).

More generally, we can use the following alternative definition: for integers \(m\) and \(n\) and positive integers \(k\), \(m\) is congruent to \(n\) modulo \(k\) if and only if \(m-n\) is divisible by \(k\) (which in this setting just means that \(\dfrac{m-n}k\) is an integer).

Note that, in this setting, \(0\) is always divisible by \(k\), so we have

\(m=n \Rightarrow m \equiv n ~~ (\mathrm{mod}~k)\,,\)

but this is only a one-way implication: the converse is false (as several of our examples above show).

One of the great things about modular arithmetic is the way it works with sums, products and powers. For example, working modulo \(10\), we can quickly determine the last decimal digit of \(3^{2001}\).

Because \(3^4 = 81 \equiv 1 ~~ (\mathrm{mod}~10)\), the rules of modular arithmetic (which I'll explain in more details elsewhere) tell us that

\(3^{2001} = 3 \times 3^{2000} = 3 \times (3^4)^{500} \equiv 3 \times 1^{500} = 3 ~~ (\mathrm{mod}~10)\,\),

and so the last decimal digit is \(3\).

You can also discover this by spotting the repeating pattern in the final digits of powers of \(3\), as this pattern repeats with period \(4\). But the modular arithmetic approach gives a clear reason for this.

Another approach is to notice that \(3^2=9 \equiv -1 ~~ (\mathrm{mod}~10)\), and so

\(3^{2001} = 3 \times 3^{2000} = 3 \times (3^2)^{1000} \equiv 3 \times (-1)^{1000} = 3 ~~ (\mathrm{mod}~10)\,\),

as before.

If you are impatient to learn more, then you can look up modular arithmetic or clock arithmetic on the web. There are many resources available. But if you want to see how I introduce it to first-year undergraduates at the University of Nottingham, you can look at my archives of videos for the module Foundations of Pure Mathematics (FPM). In particular, the video lectures from 2020-21 are available at https://tinyurl.com/fpmvod20-21, and I introduced modular arithmetic and its applications in lectures 8, 9 and 9b (along with some rather more abstract material about relations on sets, which you don't need to understand fully at this point unless you want to!).