Introduction to Modular Arithmetic, Part 2

See all posts in this series

In this part, we revise some of the material from Part 1 (with some more examples), and we discuss some of the basic properties of congruence modulo \(k,\) including reflexivity, symmetry and transitivity.

For the purposes of these posts, we will take it as standard that if you multiply or add two integers the result is always an integer. (We have to start somewhere!)

We begin by recalling the main two definitions we need, as explained in Part 1.

Definition: For an integer \(n\) and a positive integer \(m\), we say that \(n\) is divisible by \(m\) if (and only if) \(\frac nm\) is an integer.

Note: here \(n\) can be positive, negative or zero, but we will not look at divisibility by negative integers (or by zero, of course). There are other definitions of "divisible" which are probably better when you look at more abstract algebra later, but this relatively elementary definition is good enough for us here.

Definition: Let \(a\) and \(b\) be integers, and let \(k\) be a positive integer. Then we say that \(a\) is congruent to \(b\) modulo \(k\), and we write

\(a \equiv b ~~(\mathrm{mod}~k)\)

if (and only if) \(a-b\) is divisible by \(k\).
Equivalently, \(a \equiv b ~~(\mathrm{mod}~k)\) if and only if \(a\) and \(b\) leave the same remainder when you divide them by \(k\).

We saw plenty of examples in Part 1. But here are a few more.

• \(357 \equiv 127 ~~(\mathrm{mod}~10)\), because \(357-127=230\), which is divisible by \(10\), or (with the other definition) because both leave remainder \(7\) when you divide by \(10\).
• \(-16 \equiv 34 ~~(\mathrm{mod}~10)\), because \({-16} - 34 = -50\), which is divisible by \(10\). With the other definition, you need to know that, officially, because \(-16 = (-2) \times 10 +4\), the remainder when you divide \(-16\) by \(10\) is \(4\), and not \(-6\). (We require the remainder when you divide by \(10\) to be a non-negative integer that is strictly less than \(10\).)
• \(39 \equiv 60 ~~(\mathrm{mod}~7)\), because \(39-60 = {-21}\), which is divisible by \(7\) (or because they both leave remainder \(4\) when you divide by \(7\)).

We also noted in Part 1 that, for integers \(a\) and \(b\) and positive integers \(k\),

if \(a=b\), then \(a \equiv b ~~(\mathrm{mod}~k)\),

but the converse of this is not true (as many examples above show).

OK, so far that is all revision of Part 1. Our next task is to establish some of the good behaviour of congruence modulo \(k\). The first thing is that (for any particular positive integer \(k\)), congruence modulo \(k\) is an "equivalence relation". However I don't want to discuss equivalence relations in this post, so I will just list (and name) the relevant three properties here.

Let \(a,b,c\) be integers and let \(k\) be a positive integer. Then we always have the following.

Reflexivity: \(a \equiv a ~~(\mathrm{mod}~k)\).

Symmetry: if \(a \equiv b ~~(\mathrm{mod}~k)\), then \(b \equiv a ~~(\mathrm{mod}~k)\).

Transitivity: if \(a \equiv b ~~(\mathrm{mod}~k)\) and \(b \equiv c ~~(\mathrm{mod}~k)\), then \(a \equiv c ~~(\mathrm{mod}~k)\).

You can prove these three properties using either of our two definitions of congruence modulo \(k\), but it is essentially immediate if you use the "same remainder when you divide by \(k\)" definition. Also, reflexivity is just another way to state our one way implication mentioned above that if \(a = b\), then \(a \equiv b ~~(\mathrm{mod}~k)\). We leave the details to the reader. (But let me know if you want me to say more!)

This is helpful, because we can now say things like

\(3 \times 12 = 36 \equiv 16 \equiv 6~~(\mathrm{mod}~10)\), and so \(3 \times 12 \equiv 6~~ (\mathrm{mod}~10)\) (by transitivity) and \(6 \equiv 3 \times 12~~(\mathrm{mod}~10)\) (by symmetry).

These deductions don't look particularly exciting, because the conclusions are obviously true anyway, but they do show how equality, symmetry and transitivity can be used. If you look back at Part 1, you will see that equality and transitivity are particularly useful once we start looking at expressions involving (for example) large powers of positive integers.

In Part 3 we will confirm that modular arithmetic works well with sums and products, as claimed in Part 1. We'll also have a look at powers, where some care is needed.