The Operation mod

Section 3.4 The Operation \(mod\)

In this section we study the properties of the operation \(\fmod\) and show how these can be applied. The properties will seem awkward at first but will turn out to be powerful tools in computations when numbers get larger. In the video in Figure 3.4.1 we give an overview of the properties of \(\fmod\) covered in this section.

🔗

Figure 3.4.1. The operation \(\fmod\) by Matt Farmer and Stephen Steward

🔗

Before we get to the properties we recall how to compute \(\fmod\) and make some observations about the behavior of \(\fmod\text{.}\)

🔗

Subsection Computing \(\fmod\)

Recall that \(a\fmod b\) is the remainder when \(a\) is divided by \(b\) (see Definition 3.2.14). The division algorithm (Algorithm 3.2.2 and Algorithm 3.2.8) gives the quotient and remainder of a division. Another method is calculator long division, which we presented in Strategy 3.3.1.

🔗

In the next examples, we compute a remainder by inspection, with the division algorithm, and with calculator long division.

🔗

Example 3.4.2. Three methods for computing \(41\fmod 13\).

We compute \(41\fmod 13\) in three different ways. The number \(41 \fmod 13\) is the remainder of the division of \(41\) by \(13\text{.}\)

Method 1 the trained eye.
The largest multiple of 13 that is less than 41 is 39. The difference between 41 and 39 is 2, this is the remainder of the division of 41 by 13. Thus 41 mod 13 = 2.
🔗

🔗
Method 2 calculator long division.
We have \(41\div 13=3.153\dots\text{.}\) So the quotient from the decision of \(41\) by \(13\) is the largest integer that is less than \(3.153\dots\text{,}\) which is \(3\text{.}\) The remainder is \(41-3\cdot 13 = 41-39 = 2\text{.}\) Thus \(41 \mod 13 = 2\text{.}\)
🔗

🔗
Method 3 division algorithm.

We subtract \(13\) until we get a number in the remainder target range from \(0\) to \(13-1=12\text{:}\)

\begin{align*} 41-13\amp =28\\ 28-13\amp =15\\ 15-13\amp =2 \end{align*}

As \(2\) is in the remainder target range from \(0\) to \(13-1=12\) it is the remainder. Thus 41 mod 13 = 2.

🔗

🔗

🔗

Example 3.4.3. Three methods for computing \(-41\fmod 13\).

We compute \(-41\fmod 13\) in three different ways. The number \(-41 \fmod 13\) is the remainder of the division of \(-41\) by \(13\text{.}\)

Method 1 the trained eye.
The smallest multiple of \(13\) that is greater than \(41\) is \(52\text{.}\) The sum of \(-41\) and \(52\) is \(11\text{,}\) this is the remainder of the division of \(-41\) by \(13\text{.}\) Thus \(-41 \fmod 13 = 11\text{.}\)
🔗

🔗
Method 2 calculator long division.
We have \(-41\div 13=-3.153\dots\text{.}\) So the quotient of the division of \(41\) by \(13\) is the largest integer that is less than \(-3.153\dots\) which is \(-4\text{.}\) The remainder is \(-41+4\cdot 13 = -41+52 = 11\text{.}\) Thus \(-41 \fmod 13 = 11\text{.}\)
🔗

🔗
Method 3 division algorithm.

We add \(13\) until we get a number in the remainder target range from \(0\) to \(13-1=12\text{:}\)

\begin{align*} -41+13\amp =-28\\ -28+13\amp =-15\\ -15+13\amp =-2\\ -2+13\amp =11 \end{align*}

As \(11\) is in the remainder target range from \(0\) to \(13-1=12\) it is the remainder. Thus -41 mod 13 = 11.

🔗

🔗

🔗

The three methods are also subject of the video in Figure 3.4.4.

🔗

Figure 3.4.4. How to compute \(\fmod\) by Frances Clerk

🔗

Subsection Some observations

A pattern appears when we find the remainders of consecutive integers divided by the same number. The next two examples show that the remainders repeat periodically.

🔗

Example 3.4.5. Integers modulo three.

\begin{align*} 0\fmod 3\amp =0 \\ 1\fmod 3\amp =1 \\ 2\fmod 3\amp =2\\ 3\fmod 3\amp =0 \\ 4\fmod 3\amp =1 \\ 5\fmod 3\amp =2\\ 6\fmod 3\amp =0 \\ 7\fmod 3\amp =1 \\ 8\fmod 3\amp =2 \end{align*}

🔗

Example 3.4.6. Integers modulo two.

\begin{align*} 0\fmod 2\amp =0 \\ 1\fmod 2\amp =1 \\ 2\fmod 2\amp =0\\ 3\fmod 2\amp =1 \\ 4\fmod 2\amp =0 \\ 5\fmod 2\amp =1\\ 6\fmod 2\amp =0 \\ 7\fmod 2\amp =1 \\ 8\fmod 2\amp =0 \end{align*}

🔗

The remainder of division by \(2\) is an integer that is greater than or equal to \(0\) and less than \(2\text{,}\) that is, it is either \(0\) or \(1\text{.}\) We use this to define two familiar terms.

🔗

Definition 3.4.7.

An integer \(n\) is even means that \(n \fmod 2 = 0\text{.}\)

🔗

Definition 3.4.8.

An integer \(n\) is odd means that \(n \fmod 2 = 1\text{.}\)

🔗

Subsection Properties of \(\fmod\)

Now we study some properties of the operation \(\fmod\text{.}\) In particular, we are interested in the behavior of \(\fmod\) in sums and products.

🔗

To get an idea how \(\fmod\) behaves under addition we look at an example.

🔗

Example 3.4.9. Addition and \(\fmod\).

We have

\begin{equation*} (11+5) \fmod 7 = 16 \fmod 7 = 2. \end{equation*}

Let’s see whether we can distribute \(\fmod\) over the addition.

\begin{equation*} (11 \fmod 7) + (5\fmod 7) = 4 + 5 = 9. \end{equation*}

We see that

\begin{equation*} (11 \fmod 7) + (5\fmod 7) \ne (11+5) \fmod 7. \end{equation*}

But \(9\fmod 7=2\text{.}\) Computing \(\fmod 7\) once more gives equality:

\begin{equation*} ((11 \fmod 7) + (5\fmod 7))\fmod 7 = (4 + 5)\fmod 7 = 11 \fmod 7=2. \end{equation*}

So,

\begin{equation*} ((11 \fmod 7) + (5\fmod 7))\fmod 7 = (11+5) \fmod 7. \end{equation*}

🔗

We use the pattern in the example to state a theorem about addition with the operation \(\fmod\text{.}\)

🔗

Theorem 3.4.10.

Let \(a\) and \(b\) be integers, and let \(m\) be a natural number. Then

\begin{equation*} (a+b)\fmod m=\bigl((a\fmod m)+(b\fmod m)\bigr)\fmod m \end{equation*}

🔗

Proof.

We have that

\begin{align*} a\amp =(a \fmod m)+(s\cdot m) \text{ for some integer } s, \text{ and }\\ b\amp =(b \fmod m)+(t\cdot m) \text{ for some integer } t\text{.} \end{align*}

🔗

With the notation above, we have

🔗

\((a+b)\fmod m\) \(=\bigl(((a \fmod m)+(s\cdot m))+((b \fmod m)+(t\cdot m))\bigr)\fmod m\) \(=\bigl((a \fmod m)+(b \fmod m)+(s+t)\cdot m\bigr)\fmod m\) \(=\bigl((a \fmod m)+(b \fmod m)\bigr)\fmod m\)

🔗

Example 3.4.11. Addition with and without Theorem 3.4.10.

We show Theorem 3.4.10 with an example. We compute \((10+20)\fmod 7\) in two ways: directly and by applying the theorem.

\(\displaystyle (10+20)\fmod 7 = 30 \fmod 7 = 2\)
🔗

🔗
\((10+20)\fmod 7\)\(= \left((10 \fmod 7)+(20 \fmod 7)\right) \fmod 7\)\(= (3+6)\fmod 7\)\(= 9\fmod 7 =2\)
🔗

🔗

🔗

Using the theorem may seem less direct right now. Its value becomes clearer when calculations are more involved. The theorem can also evaluate expressions when we know only the remainders.

🔗

Problem 3.4.12. Apply Theorem 3.4.10.

Let \(a\) and \(b\) be integers with \(a\fmod 113=29\) and \(b\fmod 113=100\text{.}\) Compute \((a+b)\fmod 113\text{.}\)

🔗

Solution.

By Theorem 3.4.10 we have

\begin{equation*} (a+b)\fmod 113 = \left((a\fmod 113)+(b\fmod 113)\right) \fmod 113 \end{equation*}

🔗

As we know that \(a\fmod 113=29\) and \(b\fmod 113=100\) we can replace \(a\fmod 113\) by \(29\) and \(b\fmod 113\) by \(100\text{.}\) Copying what we have so far and evaluating we get:

🔗

\((a+b)\fmod 113\) \(=\left((a\fmod 113)+(b\fmod 113)\right) \fmod 113\) \(= (29+100)\fmod 113\) \(= 129 \fmod 113 = 16\)

🔗

Next we explore how multiplication and \(\fmod\) interact.

🔗

Example 3.4.13. Multiplication and \(\fmod\).

We have

\begin{equation*} (11\cdot 5) \fmod 7 = 55 \fmod 7 = 6. \end{equation*}

Let’s see whether we can distribute \(\fmod\) over multiplication.

\begin{equation*} (11 \fmod 7) \cdot (5\fmod 7) = 4 \cdot 5 = 20. \end{equation*}

We see that

\begin{equation*} (11 \fmod 7) \cdot (5\fmod 7) \ne (11\cdot 5) \fmod 7. \end{equation*}

But \(20\fmod 7=6\text{.}\) Computing \(\fmod 7\) once more gives equality:

\begin{equation*} ((11 \fmod 7) \cdot (5\fmod 7))\fmod 7 = (4 \cdot 5)\fmod 7 = 20 \fmod 7=6. \end{equation*}

So,

\begin{equation*} ((11 \fmod 7) \cdot (5\fmod 7))\fmod 7 = (11\cdot 5) \fmod 7. \end{equation*}

🔗

The pattern in the example suggests that a theorem like Theorem 3.4.10 also holds for multiplication:

🔗

Theorem 3.4.14.

Let \(a\) and \(b\) be integers, and let \(m\) be a natural number. Then

\begin{equation*} (a\cdot b)\fmod m=\bigl((a\fmod m)\cdot(b\fmod m)\bigr)\fmod m\text{.} \end{equation*}

🔗

Proof.

There are integers \(s\) and \(t\) such that

\begin{equation*} a =(a \fmod m)+(s\cdot m) \end{equation*}

and

\begin{equation*} b =(b \fmod m)+(t\cdot m). \end{equation*}

Thus \((a\cdot b)\fmod m\) \(=\bigl(((a \fmod m)+s\cdot m)\cdot ((b \fmod m)+t\cdot m)\bigr)\fmod m\) \(= \bigl((a \fmod m)\cdot(b \fmod m)\) \(\qquad + (a \fmod m) \cdot t\cdot m + s\cdot m \cdot (b \fmod m) + s\cdot m \cdot t\cdot m \bigr) \fmod m\) \(=\bigl((a \fmod m)\cdot(b \fmod m)\) \(\qquad +\bigl((a \fmod m) \cdot t + s \cdot (b \fmod m) + s\cdot m \cdot t\bigr)\cdot m\bigr) \fmod m\) \(=\bigl((a \fmod m)\cdot(b \fmod m)\bigr)\fmod m\)

🔗

Subsection Applying the properties of \(\fmod\)

Theorem 3.4.10 and Theorem 3.4.14 are especially useful for computing \(\fmod\) with larger numbers.

🔗

Example 3.4.15. Multiplication with and without Theorem 3.4.14.

We compute \((20\cdot 10)\fmod 7\) in two ways.

When we compute

\begin{equation*} (10\cdot 20)\fmod 7=200\fmod 7=4\text{,} \end{equation*}

we have to find the remainder of the division of \(200\) by \(7\text{.}\)

🔗

🔗
With Theorem 3.4.14 we get
🔗

\((20\cdot 10)\fmod 7\) \(=\left((20\fmod 7)\cdot(10\fmod 7)\right)\fmod 7\) \(=(6\cdot 3)\fmod 7=18\fmod 7=4\)
🔗

which is longer but easier to compute, since we can easily find \(20\fmod 7\) and \(10\fmod 7\text{.}\)
🔗

🔗

🔗

Example 3.4.16. Applying Theorem 3.4.10 and Theorem 3.4.14.

We compute \((61+(9\cdot 12))\fmod 7\text{.}\) First, we evaluate the inner parenthesis and then the outer parenthesis. By Theorem 3.4.10 and Theorem 3.4.14 we have

🔗

\(\left(61+(9\cdot 12)\right)\fmod 7\) \(=\left(61\fmod 7+\left((9 \fmod 7)\cdot (12 \fmod 7)\right)\fmod 7\right)\fmod 7\) \(= \left(5+\left((2\cdot 5)\fmod 7\right)\right)\fmod 7\) \(= \left(5+(10 \fmod 7)\right)\fmod 7\) \(=(5+3)\fmod 7 = 8 \fmod 7=1\)

🔗

Example 3.4.17. Smaller but more calculations.

With Calculator long division we compute:

\(\displaystyle 8082 \fmod 17 = 7\)
🔗

🔗
\(\displaystyle 4540 \fmod 17= 1\)
🔗

🔗
\(\displaystyle 4496 \fmod 17= 8\)
🔗

🔗

🔗

Knowing these numbers and applying Theorem 3.4.10 and Theorem 3.4.14 we find the following without having to add or multiply large numbers.

\((8082\cdot 4540) \fmod 17 \) \(= \left((8082\fmod 17)\cdot(4540\fmod 17)\right) \fmod 17\) \(=(7\cdot 1)\fmod 17 = 7\)
🔗

🔗
\((4540+4496) \fmod 17 \) \(= \left((4540\fmod 17)+(4496\fmod 17)\right) \fmod 17 \) \(= (1+8) \fmod 17 = 9\)
🔗

🔗
\((8082\cdot 4540 + 4496) \fmod 17\) \(= \left(\left((8082\cdot 4540) \fmod 17 \right)+ (4496\fmod 17)\right)\fmod 17 \) \(= (7+8)\fmod 17 = 15\)
🔗

🔗
\((8082+4540+4496)\fmod 17 \) \(= \left((8082\fmod 17)+\left((4540+4496) \fmod 17\right)\right)\fmod 17 \) \(= (7+9)=16 \fmod 17=16\)
🔗

🔗

🔗

Next, we use the decimal representation of numbers to find remainders for numbers that are too large for most calculators. For a review of decimal numbers, read Section 11.1.

🔗

Problem 3.4.18. \(23829913346008023471 \fmod 100\).

Find \(23829913346008023471 \fmod 100\text{.}\)

🔗

Solution.

First notice that

\begin{equation*} 23829913346008023471=(238299133460080234\cdot 100)+71\text{.} \end{equation*}

🔗

With Theorem 3.4.10 and \(100\fmod 100=0\) we get:

🔗

\(23829913346008023471 \fmod 100 \) \(= ((238299133460080234\cdot 100)+71) \fmod 100\) \(= (((238299133460080234\cdot 100) \fmod 100)+(71 \fmod 100))\fmod 100\) \(= (0 + 71) \fmod 100 = 71\fmod 100= 71\)

🔗

Problem 3.4.19. \(23829913346008023471 \fmod 1000\).

Find \(23829913346008023471 \fmod 1000\text{.}\)

🔗

Solution.

First notice that

\begin{equation*} 23829913346008023471=(23829913346008023\cdot 1000)+471\text{.} \end{equation*}

🔗

With Theorem 3.4.10 and \(1000\fmod 1000=0\) we get:

🔗

\(23829913346008023471 \fmod 1000 \) \(= ((23829913346008023\cdot 1000)+471) \fmod 1000\) \(= (((23829913346008023\cdot 1000) \fmod 1000)+(471 \fmod 1000))\fmod 1000\) \(= (0 + 471) \fmod 1000 = 471\fmod 1000= 471\)

🔗

Problem 3.4.20. \(23829913346008023471 \fmod 20\).

Find \(23829913346008023471 \fmod 20\text{.}\)

🔗

Solution.

The smallest power of \(10\) that is divisible by \(20\) is \(10^2=100\text{.}\)

🔗

Now notice that

\begin{equation*} 23829913346008023471=(238299133460080234\cdot 100)+71\text{.} \end{equation*}

🔗

With Theorem 3.4.10 and \(100\fmod 20=0\) we get:

🔗

\(23829913346008023471 \fmod 20 \) \(= ((238299133460080234\cdot 100)+71) \fmod 20\) \(= (((238299133460080234\cdot 100) \fmod 20)+(71 \fmod 20))\fmod 20\) \(= (0 + 71) \fmod 20 = 71\fmod 20= 11\)

🔗

Problem 3.4.21. \(23829913346008023471 \fmod 5\).

Find \(23829913346008023471 \fmod 5\text{.}\)

🔗

Solution.

The smallest power of \(10\) that is divisible \(5\) is 10. So we write

\begin{equation*} 23829913346008023471=(2382991334600802347\cdot 10)+1\text{.} \end{equation*}

🔗

As \(10\fmod 5=0\) we immediately see that

\begin{equation*} 23829913346008023471 \fmod 5=(0+1)\fmod 5=1. \end{equation*}

🔗

Prev Top Next