The Operation mod

Section 3.4 The Operation $m o d$

In this section we investigate the properties of the operation

mod

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.37 we give an overview of the properties of

mod

covered in this section.

🔗

Figure 3.37. The operation $mod$ by Matt Farmer and Stephen Steward

🔗

Before we get to the properties we recall how to compute

mod

and make some observations about the behavior of

mod .

🔗

Subsection Computing $mod$

🔗

Recall that

a mod b

is the remainder of the division of

a

b

(see Definition 3.21). We have established that the division algorithm (Algorithm 3.6 and Algorithm 3.14) produces the quotient and remainder of a particular division as its output values. As an alternative method we have presented (calculator) long division in Strategy 3.1.

🔗

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

🔗

Example 3.38. Three methods for computing $41 mod 13$ .

🔗

We compute

41 mod 13

in three different ways. The number

41 mod 13

is the remainder of the division of

41

13 .

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 .$ So the quotient from the decision of $41$ by $13$ is the largest integer that is less than $3.153 \dots,$ which is $3 .$ The remainder is $41 - 3 \cdot 13 = 41 - 39 = 2 .$ Thus $41 \mod 13 = 2 .$
Method 3 division algorithm.

We subtract $13$ until we get a number in the remainder target range from $0$ to $13 - 1 = 12 :$

$\begin{aligned} 41 - 13 & = 28 \\ 28 - 13 & = 15 \\ 15 - 13 & = 2 \end{aligned}$

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.39. Three methods for computing $- 41 mod 13$ .

🔗

We compute

- 41 mod 13

in three different ways. The number

- 41 mod 13

is the remainder of the division of

- 41

13 .

Method 1 the trained eye.
The smallest multiple of $13$ that is greater than $41$ is $52 .$ The sum of $- 41$ and $52$ is $11,$ this is the remainder of the division of $- 41$ by $13 .$ Thus $- 41 mod 13 = 11 .$
Method 2 calculator long division.
We have $- 41 \div 13 = - 3.153 \dots .$ So the quotient of the division of $41$ by $13$ is the largest integer that is less than $- 3.153 \dots$ which is $- 4 .$ The remainder is $- 41 + 4 \cdot 13 = - 41 + 52 = 11 .$ Thus $- 41 mod 13 = 11 .$
Method 3 division algorithm.

We add $13$ until we get a number in the remainder target range from $0$ to $13 - 1 = 12 :$

$\begin{aligned} - 41 + 13 & = - 28 \\ - 28 + 13 & = - 15 \\ - 15 + 13 & = - 2 \\ - 2 + 13 & = 11 \end{aligned}$

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

🔗

Figure 3.40. How to compute $mod$ by Frances Clerk

🔗

Subsection Some observations

🔗

An interesting pattern occurs when we compute the remainder of consecutive integers from the divisions by the same number. As illustrated in the following two examples, the remainders repeat in a periodic fashion.

🔗

Example 3.41. Integers modulo three.

🔗

\begin{aligned} 0 mod 3 & = 0 \\ 1 mod 3 & = 1 \\ 2 mod 3 & = 2 \\ 3 mod 3 & = 0 \\ 4 mod 3 & = 1 \\ 5 mod 3 & = 2 \\ 6 mod 3 & = 0 \\ 7 mod 3 & = 1 \\ 8 mod 3 & = 2 \end{aligned}

🔗

Example 3.42. Integers modulo two.

🔗

\begin{aligned} 0 mod 2 & = 0 \\ 1 mod 2 & = 1 \\ 2 mod 2 & = 0 \\ 3 mod 2 & = 1 \\ 4 mod 2 & = 0 \\ 5 mod 2 & = 1 \\ 6 mod 2 & = 0 \\ 7 mod 2 & = 1 \\ 8 mod 2 & = 0 \end{aligned}

🔗

The remainder of division by

2

is an integer that is greater than or equal to

0

and less than

2,

that is, it is either

0

1 .

We use this to define two familiar terms.

🔗

Definition 3.43.

🔗

An integer

n

is even means that

n mod 2 = 0 .

🔗

Definition 3.44.

🔗

An integer

n

is odd means that

n mod 2 = 1 .

🔗

Subsection Properties of $mod$

🔗

We now investigate some properties of the operation

mod .

In particular, we are interested in the behavior of

mod

in sums and products.

🔗

To get an idea how

mod

behaves under addition we look at an example.

🔗

Example 3.45. Addition and $mod$ .

🔗

We have

(11 + 5) mod 7 = 16 mod 7 = 2.

🔗

Let’s try we whether we can distribute

mod

over the addition.

(11 mod 7) + (5 mod 7) = 4 + 5 = 9.

🔗

We see that

(11 mod 7) + (5 mod 7) \neq (11 + 5) mod 7.

🔗

But we notice that

9 mod 7 = 2 .

So computing

mod 7

once more will yield equality:

((11 mod 7) + (5 mod 7)) mod 7 = (4 + 5) mod 7 = 11 mod 7 = 2.

🔗

So, we have

((11 mod 7) + (5 mod 7)) mod 7 = (11 + 5) mod 7.

🔗

We build upon our observations in the example to formulate a theorem about addition in combination with the operation

mod .

🔗

Theorem 3.46.

🔗

Let

a

and

b

be integers, and let

m

be a natural number. Then

(a + b) mod m = ((a mod m) + (b mod m)) mod m

Proof.

We have that

\begin{aligned} a & = (a mod m) + (s \cdot m) for some integer s, and \\ b & = (b mod m) + (t \cdot m) for some integer t . \end{aligned}

With the notation above, we have

(a + b) mod m

= (((a mod m) + (s \cdot m)) + ((b mod m) + (t \cdot m))) mod m

= ((a mod m) + (b mod m) + (s + t) \cdot m) mod m

= ((a mod m) + (b mod m)) mod m

🔗

Example 3.47. Addition with and without Theorem 3.46.

🔗

We illustrate Theorem 3.46 with an example. We compute

(10 + 20) mod 7

in two ways, namely directly and applying the theorem.

$(10 + 20) mod 7 = 30 mod 7 = 2$
$(10 + 20) mod 7$ $= ((10 mod 7) + (20 mod 7)) mod 7$ $= (3 + 6) mod 7$ $= 9 mod 7 = 2$

🔗

Using the theorem may seem more awkward right now. When calculations get more involved its value will become more apparent. The theorem also can be used to evaluate expressions when we only know the remainders.

🔗

Problem 3.48. Apply Theorem 3.46.

🔗

Let

a

and

b

be integers with

a mod 113 = 29

and

b mod 113 = 100 .

Compute

(a + b) mod 113 .

Solution.

By Theorem 3.46 we have

(a + b) mod 113 = ((a mod 113) + (b mod 113)) mod 113

As we know that

a mod 113 = 29

and

b mod 113 = 100

we can replace

a mod 113

29

and

b mod 113

100 .

Copying what we have so far and evaluating we get:

(a + b) mod 113

= ((a mod 113) + (b mod 113)) mod 113

= (29 + 100) mod 113

= 129 mod 113 = 16

🔗

Next we explore how multiplication and

mod

interact.

🔗

Example 3.49. Multiplication and $mod$ .

🔗

We have

(11 \cdot 5) mod 7 = 55 mod 7 = 6.

🔗

Let’s try we whether we can distribute

mod

over the addition.

(11 mod 7) \cdot (5 mod 7) = 4 \cdot 5 = 20.

🔗

We see that

(11 mod 7) \cdot (5 mod 7) \neq (11 \cdot 5) mod 7.

🔗

But we notice that

20 mod 7 = 6 .

So computing

mod 7

once more will yield equality:

((11 mod 7) \cdot (5 mod 7)) mod 7 = (4 \cdot 5) mod 7 = 20 mod 7 = 3.

🔗

So, we have

((11 mod 7) \cdot (5 mod 7)) mod 7 = (11 \cdot 5) mod 7.

🔗

The observations made in the example suggests that a theorem analogous to Theorem 3.46 holds for multiplication. Indeed we have:

🔗

Theorem 3.50.

🔗

Let

a

and

b

be integers, and let

m

be a natural number. Then

(a \cdot b) mod m = ((a mod m) \cdot (b mod m)) mod m .

Proof.

There are integers

s

and

t

such that

a = (a mod m) + (s \cdot m)

and

b = (b mod m) + (t \cdot m) .

Thus

(a \cdot b) mod m

= (((a mod m) + s \cdot m) \cdot ((b mod m) + t \cdot m)) mod m

= ((a mod m) \cdot (b mod m)

+ (a mod m) \cdot t \cdot m + s \cdot m \cdot (b mod m) + s \cdot m \cdot t \cdot m) mod m

= ((a mod m) \cdot (b mod m)

+ ((a mod m) \cdot t + s \cdot (b mod m) + s \cdot m \cdot t) \cdot m) mod m

= ((a mod m) \cdot (b mod m)) mod m

🔗

In Checkpoint 3.51 decide whether statements about

mod

are true or false. If the statement is false give a counterexample, otherwise leave the box empty.

Checkpoint 3.51. Properties of $mod$ .

Decide whether the following statements are true or false. If the statement is false give a counterexample, otherwise leave the box empty.

(1)

select
The statement is true
The statement is false

For all integers

a

and

b

we have

(a \cdot b) mod 6 = ((a mod 6) \cdot (b mod 6)) mod 6

Counterexample: The statement is false, because for the integer

a =

we have

(a \cdot 5) mod 6 \neq ((a mod 6) \cdot (5 mod 6)) mod 6 .

(2)

select
The statement is true
The statement is false

For all integers

a

and

b

we have

(a + b) mod 20 = (a mod 20) + (b mod 20)

Counterexample: The statement is false, because for the integer

a =

we have

(a + 5) mod 20 \neq (a mod 20) + (5 mod 20) .

(3)

select
The statement is true
The statement is false

For all integers

a

and all

b

we have

(a + b) mod 6 = a + b

Counterexample: The statement is false, because for the integer

a =

we have

(a + 3) mod 6 \neq a + 3 .

🔗

Subsection Applying the properties of $mod$

🔗

Theorem 3.46 and Theorem 3.50 are particularly useful when computing

mod

with larger numbers.

🔗

Example 3.52. Multiplication with and without Theorem 3.50.

🔗

We compute

(20 \cdot 10) mod 7

in two ways.

When we compute

$(10 \cdot 20) mod 7 = 200 mod 7 = 4,$

we have to find the remainder of the division of $200$ by $7 .$
With Theorem 3.50 we get

$(20 \cdot 10) mod 7$ $= ((20 mod 7) \cdot (10 mod 7)) mod 7$ $= (6 \cdot 3) mod 7 = 18 mod 7 = 4$

which is longer but easier to compute, since we can easily find $20 mod 7$ and $10 mod 7 .$

🔗

Example 3.53. Applying Theorem 3.46 and Theorem 3.50.

🔗

We compute

(61 + (9 \cdot 12)) mod 7 .

We first evaluate the inner parenthesis and then the outer parenthesis. By Theorem 3.46 and Theorem 3.50 we have

🔗

(61 + (9 \cdot 12)) mod 7

= (61 mod + ((9 mod 7) \cdot (12 mod 7)) mod 7) mod 7

= (5 + ((2 \cdot 5) mod 7)) mod 7

= (5 + (10 mod 7)) mod 7

= (5 + 3) mod 7 = 8 mod 7 = 1

🔗

Example 3.54. Smaller but more calculations.

🔗

With Calculator long division we compute:

$8082 mod 17 = 7$
$4540 mod 17 = 1$
$4496 mod 17 = 8$

🔗

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

$(8082 \cdot 4540) mod 17$ $= ((8082 mod 17) \cdot (4540 mod 17)) mod 17$ $= (7 \cdot 1) mod 17 = 7$
$(4540 + 4496) mod 17$ $= ((4540 mod 17) \cdot (4496 mod 17)) mod 17$ $= (1 + 8) mod 17 = 9$
$(8082 \cdot 4540 + 4496) mod 17$ $= (((8082 \cdot 4540) mod 17) + (4496 mod 17)) mod 7$ $= (7 + 8) mod 17 = 0$
$(8082 + 4540 + 4496) mod 17$ $= ((8082 mod 17) + ((4540 + 4496) mod 17)) mod 17$ $= (7 + 9) = 16 mod 17 = 16$

🔗

In Checkpoint 3.55 apply properties the properties of

mod

to conduct computations modulo a given integer, when the values are only known modulo that integer.

Checkpoint 3.55. Apply properties of $mod$ .

Let

a

be an integer.

Suppose that the remainder when

a

is divided by

6

0

and the remainder when

b

is divided by

6

2 .

That is,

a mod 6 = 0

and

b mod 6 = 2.

Find:

(a + a) mod 6

(a + b) mod 6

(a \cdot b) mod 6

(a + 5) mod 6

(5 \cdot b) mod 6

🔗

In the following me make use of the decimal representation of numbers, to find remainders of divisions of numbers that would be to large to handle for most calculators. If you need a refresher on decimal numbers, flip ahead and read Section 11.1.

🔗

Problem 3.56. $23829913346008023471 mod 100$ .

🔗

Find

23829913346008023471 mod 100 .

Solution.

First notice that

23829913346008023471 = (238299133460080234 \cdot 100) + 71 .

With Theorem 3.46 and

100 mod 100 = 0

we get:

23829913346008023471 mod 100

= ((238299133460080234 \cdot 100) + 71) mod 100

= (((238299133460080234 \cdot 100) mod 100) + (71 mod 100)) mod 100

= (0 + 71) mod 100 = 71 mod 100 = 71

🔗

Problem 3.57. $23829913346008023471 mod 1000$ .

🔗

Find

23829913346008023471 mod 1000 .

Solution.

First notice that

23829913346008023471 = (23829913346008023 \cdot 1000) + 471 .

With Theorem 3.46 and

1000 mod 1000 = 0

we get:

23829913346008023471 mod 1000

= ((23829913346008023 \cdot 1000) + 471) mod 1000

= (((23829913346008023 \cdot 1000) mod 1000) + (471 mod 1000)) mod 1000

= (0 + 471) mod 1000 = 471 mod 1000 = 471

🔗

Problem 3.58. $23829913346008023471 mod 20$ .

🔗

Find

23829913346008023471 mod 20 .

Solution.

The smallest power of

10

that is divisible by

20

10^{2} = 100 .

Now notice that

23829913346008023471 = (238299133460080234 \cdot 100) + 71 .

With Theorem 3.46 and

100 mod 20 = 0

we get:

23829913346008023471 mod 20

= ((238299133460080234 \cdot 100) + 71) mod 20

= (((238299133460080234 \cdot 100) mod 20) + (71 mod 20)) mod 20

= (0 + 71) mod 20 = 71 mod 20 = 11

🔗

Problem 3.59. $23829913346008023471 mod 5$ .

🔗

Find

23829913346008023471 mod 5 .

Solution.

The smallest power of

10

that is divisible

5

is 10. So we write

23829913346008023471 = (2382991334600802347 \cdot 10) + 1 .

10 mod 5 = 0

we immediately see that

23829913346008023471 mod 5 = (0 + 1) mod 5 = 1.

🔗

Try for yourself in Checkpoint 3.60.

Checkpoint 3.60. Large numbers and $mod$ .

We can write

2011317099 =

\cdot 100 +

Because

99 mod 2

= we have

2011317099 mod 2

= .

Because

99 mod 4

= we have

2011317099 mod 4

= .

Because

99 mod 5

= we have

2011317099 mod 5

= .

Because

99 mod 10

= we have

2011317099 mod 10

= .

Because

99 mod 20

= we have

2011317099 mod 20

= .

Because

99 mod 25

= we have

2011317099 mod 25

= .

Because

99 mod 100

= we have

2011317099 mod 100

= .

Hint.

Example:

1234567 = 12345 \cdot 100 + 67

In the following each

?

can be any number from

0

9 .

We have

2011317099 mod 10 = 9 mod 10

Thus, because

2

and

5

divide

10,

also

2011317099 mod 2 = 9 mod 2

and

2011317099 mod 5 = 9 mod 5

Similarly

2011317099 mod 100 = 99 mod 100

Thus, because

4

and

20

and

25

divide

100,

also

2011317099 mod 4 = 99 mod 4

and

2011317099 mod 20 = 99 mod 20

and

2011317099 mod 25 = 99 mod 25 .

Prev Top Next

Section 3.4 The Operation mod

Subsection Computing mod

Example 3.38. Three methods for computing 41mod13.

Example 3.39. Three methods for computing −41mod13.

Subsection Some observations

Example 3.41. Integers modulo three.

Example 3.42. Integers modulo two.

Definition 3.43.

Definition 3.44.

Subsection Properties of mod

Example 3.45. Addition and mod.

Theorem 3.46.

Proof.

Example 3.47. Addition with and without Theorem 3.46.

Problem 3.48. Apply Theorem 3.46.

Example 3.49. Multiplication and mod.

Theorem 3.50.

Proof.

Checkpoint 3.51. Properties of mod.

Subsection Applying the properties of mod

Example 3.52. Multiplication with and without Theorem 3.50.

Example 3.53. Applying Theorem 3.46 and Theorem 3.50.

Example 3.54. Smaller but more calculations.

Checkpoint 3.55. Apply properties of mod.

Problem 3.56. 23829913346008023471mod100.

Problem 3.57. 23829913346008023471mod1000.

Problem 3.58. 23829913346008023471mod20.

Problem 3.59. 23829913346008023471mod5.

Checkpoint 3.60. Large numbers and mod.

Section 3.4 The Operation $m o d$

Subsection Computing $mod$

Example 3.38. Three methods for computing $41 mod 13$ .

Example 3.39. Three methods for computing $- 41 mod 13$ .

Subsection Properties of $mod$

Example 3.45. Addition and $mod$ .

Example 3.49. Multiplication and $mod$ .

Checkpoint 3.51. Properties of $mod$ .

Subsection Applying the properties of $mod$

Checkpoint 3.55. Apply properties of $mod$ .

Problem 3.56. $23829913346008023471 mod 100$ .

Problem 3.57. $23829913346008023471 mod 1000$ .

Problem 3.58. $23829913346008023471 mod 20$ .

Problem 3.59. $23829913346008023471 mod 5$ .

Checkpoint 3.60. Large numbers and $mod$ .