8.2 Modular Arithmetic: A Case Study

Let us consider a context in which different integers can be seen to be the “same".

Consider an analogue clock.

Figure 8.1: Analogue clock showing 1:00 (or 13:00)

At 1 o’clock, a digital clock may read either 1:00 or 13:00 while from an analogue perspective, these are the same time. Alternatively, if you are scheduling something in 24 hours time, then that is equivalent to scheduling something at the same time the next day.

We can formalise and generalise these ideas. Recall that any integer $a$ can be written as $a=qd+r$ where $d$ is some integer divisor and $r$ is the remainder: an integer such that $0\leq r<d$ .

For example $25=3\times 7+4$ . Hence $4$ is the remainder when $25$ is divided by $7$ . The quotient, $q$ , is $3$ .

At first glance this appears silly: why not just write $\frac{25}{7}=3+\frac{4}{7}$ ? The reason is that by writing $25=3\times 7+4$ all terms remain integers. That is, we continue to work exclusively within the integer number system.

Note that the remainder behaves like our clock: it increases as expected until we get to an upper bound, in this case $d$ , when it then ’resets’ and starts counting up again from 0. If we only want to consider two integers as being “different” if they have different remainders (e.g. if we only wanted to keep track of the time in the day and didn’t care which day it was), we could use the language of congruence.

Definition 8.2 (Congruence).

For $m\in\mathbb{N}$ and $a,b\in\mathbb{Z}$ , we say $a$ is congruent to $b$ modulo $m$ , and write $a=b\mod m$ , or sometimes $a\equiv b\mod m$ , if there is some $q\in\mathbb{Z}$ such that $b-a=qm$ .

Example 8.3.

(a)

$13\equiv 3\mod 10$ as $13-3=10$ is divisible by 10.
(b)

As we saw with the clock, $13\equiv 1\mod 12$ as $13-1=12$ .
(c)

$71\equiv 2\mod 23$ as $71-2=69=3\times 23$ .

Note that when we work with congruent integers, we always clearly state what value $m$ we are working with. This is very important as changing the value $m$ completely changes which integers are equivalent. In particular, every integer is congruent to $0\mod 1$ .

There are a number of ways we can view congruent integers.

Theorem 8.4.

Let $m\in\mathbb{N}$ and $a,b\in\mathbb{Z}$

The following are equivalent:

(a)

$a=b\mod m$ ;
(b)

$m$ divides $a-b$ ;
(c)

$a$ and $b$ have same remainder when divided by $m$ ;
(d)

$b=qm+a$ for some $q\in\mathbb{Z}$ .

Proof.

(a) $\implies$ (d) and (d) $\implies$ (a) both follow directly from Definition 8.2.

For (d) $\implies$ (b), if $b-a=qm$ for some $q\in\mathbb{Z}$ , then $m$ is a divisor of $b-a$ by definition.

For (b) $\implies$ (c), we know there exist integers $p$ and $q$ such that $a=pm+r$ and $b=qm+s$ where $r$ and $s$ are remainders. Then $a-b=(p-q)m+(r-s)$ . If $m$ divides $a-b$ , then $r-s=0$ so $r=s$ as required.

Finally, $(c)$ $\implies$ (d) as if $a$ and $b$ have the same remainder $r$ when divided by $m$ , then $a=pm+r$ and $b=\ell m+r$ for some integers $p,\ell$ , so, substituting for $r$ , we can write $b=\ell m+(a-pm)=(\ell-p)m+a$ . As $\ell$ and $p$ are both integers, we have written $b=qm+a$ where $q=\ell-p$ is an integer.

We have therefore shown that all of these statements are equivalent to one another.

Corollary 8.5.

Every integer is congruent to exactly one of the numbers $0,1,2,\cdots,m-1\mod m$ .

Proof.

Let $n\in\mathbb{Z}$ . Then we can uniquely write $n=qm+r$ where $r$ is the remainder with $0\leq r\leq m-1$ .

Then $n-r=qm$ so, by Definition 8.2, $n=r\mod m$ which concludes the proof.

Exercise 8.6.

Working $\mod 11$ , write $58$ in three different ways.

Solution (please try for yourself before looking)

Since $58=(5\times 11)+3=(6\times 11)-8=(4\times 11)+14$ , we have

58=3=-8=14\mod 11.

Corollary 8.7.

Let $p\in\mathbb{N}$ be a divisor of $m\in\mathbb{N}$ , $p\neq 1$ , and $a=b\mod m$ , then $a=b\mod p$ .

Proof.

By assumption, we have $m=pk$ for some $k\in\mathbb{Z}$ . Moreover, as $a=b\mod m$ , then Definition 8.2 means that $a-b=qm$ for some $q\in\mathbb{Z}$ . Together, this means $a-b=qpk=(qk)p$ . As $qk\in\mathbb{Z}$ , by Definition 8.2, we therefore also have $a=b\mod p$ .

8.2.1 Modular Arithmetic Operations

Now we have objects which are equivalent, we would like to be able to combine these. Just like we can add time together without breaking our clock, we can have addition and multiplication modulo $m$ .

Proposition 8.8 (Addition and Multiplication).

If $m\in\mathbb{N}$ and $a,b,x,y\in\mathbb{Z}$ such that $a=x\mod m$ and $b=y\mod m$ , then

(a)

$-a=-x\mod m$
(b)

$a+b=x+y\mod m$
(c)

$ab=xy\mod m$
(d)

$a^{k}=x^{k}\mod m$ for every $k\in\mathbb{N}$ .

Proof.

By assumption, $m$ divides $a-x$ and $m$ divides $b-y$ .

(a)

Then $m$ divides $-(a-x)=(-a)-(-x)$ , so $-a=-x\mod m$ .
(b)

The Linear Combination Lemma implies that $m$ divides

$(a-x)+(b-y)=(a+b)-(x+y),$

and so $a+b=x-y\mod m$ .
(c)

Since $m|(a-x)$ and $m|(b-y)$ , we have $a=x+pm$ for some $p\in\mathbb{Z}$ and $b=y+qm$ for some $q\in\mathbb{Z}$ . Thus,

$ab=(x+pm)(y+qm)=xy+pmy+xqm+pqm^{2}=xy+m(py+xq+pqm),$

and so $ab=xy\mod m$ by Theorem 8.4 (part (d)).
(d)

This can be proven by induction. Let $P(n)$ be the statement that $a^{n}=x^{n}\mod m$ .

For the base case of $n=1$ , this follows from the assumption $a=x\mod m$ .

For the induction step, suppose $a^{k}=x^{k}\mod m$ for some $k\geq 1$ . Then by part (c) of this theorem with $b=a^{k}$ and $y=x^{k}$ and using the fact that $a=x\mod m$ , we have

$a\cdot a^{k}=x\cdot x^{k}\mod m.$

Thus,

$a^{k+1}=x^{k+1}\mod m.$

This proves that $P(k)\implies P(k+1)$ and thus $P(n)$ holds for all $n\in\mathbb{N}$ by induction.

Altogether, we can now define the following set.

Definition 8.9.

For $m\in\mathbb{N}$ , addition and multiplication on the set

\mathbb{Z}/m=\{0,1,\ldots,m-1\},

is defined as follows. For every $x,y\in\mathbb{Z}/m$ :

•

$x+y$ is the unique $z\in\mathbb{Z}/m$ such that $x+y=z\mod m$ .
•

$x\cdot y$ is the unique $z\in\mathbb{Z}/m$ such that $x\cdot y=z\mod m$ .

From this, we can then form addition and multiplication tables.

$+$	0	1	2	3	4
0	0	1	2	3	4
1	1	2	3	4	0
2	2	3	4	0	1
3	3	4	0	1	2
4	4	0	1	2	3

$\times$	1	2	3	4
0	0	0	0	0
1	1	2	3	4
2	2	4	1	3
3	3	1	4	2
4	4	3	2	1

Figure 8.2: Addition and Multiplication Tables modulo 5

We can then define subtraction.

Proposition 8.10.

Every $x\in\mathbb{Z}/m$ has an additive inverse i.e. there exists $y\in\mathbb{Z}/m$ such that $x+y=0\mod m$ .

Proof.

Let $x\in\mathbb{Z}/m$ and $a\in\mathbb{Z}$ such that $a=x\mod m$ . Then, by Proposition 8.8 (a), we have $-a=-x\mod m$ . Moreover, by Proposition 8.8 (b), $a-a=0=x-x\mod m$ . Finally, from Corollary 8.5, we know there exists a $y\in\mathbb{Z}/m$ such that $-x=y\mod m$ .

However, we have to be a bit more careful with the definition of division.

Proposition 8.11 (Division).

Suppose $m\in\mathbb{N}$ is coprime to $a\in\mathbb{Z}$ . Then if $x,y\in\mathbb{Z}$ such that $xa=ya\mod m$ , we have $x=y\mod m$ i.e. we can “divide” both sides of the equation by $a$ .

Proof.

Suppose $a$ and $m$ are coprime and $xa=ya\mod m$ . Then by definition 8.2, $m$ divides $xa-ya=(x-y)a$ . Since $m$ and $a$ are coprime, $m$ must divides $x-y$ , and so $x=y\mod m$ by definition.

This doesn’t work without the coprime condition. Indeed, consider multiplication modulo 6. If we take $a=2$ , then we see that $2=8\mod 6$ but $1\neq 4\mod 6$ .

We can also see this from our multiplication tables. With our usual definition of division, $\frac{a}{b}=a\cdot\frac{1}{b}=r$ , where $\frac{1}{b}$ is called the multiplicative inverse of $b$ . This is the unique real number such that $b\cdot\frac{1}{b}=\frac{1}{b}\cdot b=1$ . But the only real number we can’t divide by is 0 i.e. 0 has no multiplicative inverse, because there is no real number that we can multiply by 0 to give us 1.

We can apply a similar thinking to working modulo $m$ . We can define $b$ to be the multiplicative inverse of $a$ modulo $m$ if $ba=ab=1\mod m$ . But notice in your multiplication table modulo 6, say, that some rows (rows 0,2,3,4) don’t contain a 1 in them at all! This means there is no multiplicative inverse in $\mathbb{Z}/6$ for 0, 2, 3 and 4. These are precisely the elements in $\mathbb{Z}/6$ that are not coprime with 6.

$\times$	1	2	3	4	5
0	0	0	0	0	0
1	1	2	3	4	5
2	2	4	0	2	4
3	3	0	3	0	3
4	4	2	0	4	2
5	5	4	3	2	1

Figure 8.3: Multiplication table modulo 6

Corollary 8.12.

If $p$ is prime, then every $x\in\mathbb{Z}/p$ has both an additive and multiplicative inverse.

If a set has both well-defined addition and multiplication, and their inverses, then we call the set a field. See more in Introduction to Mathematical Analysis next term.

8.2.2 Applications of Modular Arithmetic

Congruences do let us solve some nice problems.

Exercise 8.13.

Show that the sequence given by $3n+8$ , $n\in\mathbb{N}$ contains no squares.

Solution (please try for yourself before looking)

We want to show that there is no $m\in\mathbb{Z}$ such that $m^{2}=3n+8$ for any $n\in\mathbb{N}$ . To simplify this, we consider this equation modulo 3 so, recalling $8=2\mod 3$ , we want to solve

m^{2}=2\mod 3.

We can use an exhaustive proof here:

	Case 1:	$\displaystyle\text{ If }a=0,\text{ then }a^{2}=0\mod 3.$
	Case 2:	$\displaystyle\text{ If }a=1,\text{ then }a^{2}=1\mod 3.$
	Case 3:	$\displaystyle\text{ If }a=2,\text{ then }a^{2}=4=1\mod 3.$

Any other integer is equivalent to one of these cases modulo 3 meaning there is no integer $m$ such that $m^{2}=2\mod 3$ .

Exercise 8.14.

Let $n\in\mathbb{Z}$ with digits $a_{r}a_{r-1}\ldots a_{0}$ . Show that $n$ is divisible by 3 if and only if the sum of the digits is divisible by 3.

Solution (please try for yourself before looking)

Let $n\in\mathbb{Z}$ with digits $a_{r}a_{r-1}\ldots a_{0}$ , then we can write

n=a_{0}+10a_{1}+\cdots+10^{r}a_{r}.

Note that $10=1\mod 3$ so any power of 10 is also equal to 1 mod 3. Therefore, considering this equation modulo 3 we get,

n=a_{0}+a_{1}+\cdots+a_{r}\mod 3.

Therefore $n$ is divisible by 3 (i.e. $n=0\mod 3$ ), if and only if the sum of the digits $a_{i}$ is divisible by 3.

Exercise 8.15.

Prove that the last digit of $7^{7^{1000}}$ is 7.

Solution (please try for yourself before looking)

To find the last digit of a number, we consider it modulo 10.

We therefore first consider powers of $7$ modulo 10:

	$\displaystyle 7^{1}$	$\displaystyle=7\times 1=7\mod 10$
	$\displaystyle 7^{2}$	$\displaystyle=7\times 7=9\mod 10$
	$\displaystyle 7^{3}$	$\displaystyle=7\times 9=3\mod 10$
	$\displaystyle 7^{4}$	$\displaystyle=7\times 3=1\mod 10$
	$\displaystyle 7^{5}$	$\displaystyle=7\times 1=7\mod 10$
		$\displaystyle\quad\quad\vdots$

So in general, the last digit of $7^{k}$ depends on the value of $k\mod 4$ . We therefore want to find $7^{1000}\mod 4$ . Similarly to above, we have

	$\displaystyle 7^{1}$	$\displaystyle\hskip 41.25641pt=3\mod 4$
	$\displaystyle 7^{2}$	$\displaystyle=3\times 3=1\mod 4$
	$\displaystyle 7^{3}$	$\displaystyle=3\times 1=3\mod 4$
		$\displaystyle\hskip 21.33955pt\vdots$

Hence $7^{1000}=(7^{2})^{500}=1^{500}=1\mod 4$ so $7^{7^{1000}}=7^{1}=7\mod 10$ and the last digit of $7^{7^{1000}}$ is therefore $7$ .