In this section we investigate 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.37 we give an overview of the properties of \(\fmod\) covered in this section.
Figure3.37.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{.}\)
SubsectionComputing \(\fmod\)
Recall that \(a\fmod b\) is the remainder of the division of \(a\) by \(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).
Example3.38.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{:}\)
As \(2\) is in the remainder target range from \(0\) to \(13-1=12\) it is the remainder. Thus 41 mod 13 = 2.
Example3.39.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{:}\)
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.
Figure3.40.How to compute \(\fmod\) by Frances Clerk
SubsectionSome 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.
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.
Definition3.43.
An integer \(n\) is even means that \(n \fmod 2 = 0\text{.}\)
Definition3.44.
An integer \(n\) is odd means that \(n \fmod 2 = 1\text{.}\)
SubsectionProperties of \(\fmod\)
We now investigate 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.
We build upon our observations in the example to formulate a theorem about addition in combination with the operation \(\fmod\text{.}\)
Theorem3.46.
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*}
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.
Problem3.48.Apply Theorem 3.46.
Let \(a\) and \(b\) be integers with \(a\fmod 113=29\) and \(b\fmod 113=100\text{.}\) Compute \((a+b)\fmod 113\text{.}\)
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:
\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\)
In Checkpoint 3.51 decide whether statements about \(\fmod\) are true or false. If the statement is false give a counterexample, otherwise leave the box empty.
Checkpoint3.51.Properties of \(\fmod\).
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)\bmod 6 = \left((a \bmod 6) \cdot (b \bmod 6)\right) \bmod 6\)
Counterexample: The statement is false, because for the integer \(a=\) we have \((a\cdot 5) \bmod 6 \ne \left((a \bmod 6) \cdot ( 5 \bmod 6)\right) \bmod 6\text{.}\)
(2)
select
The statement is true
The statement is false
For all integers \(a\) and \(b\) we have \((a+ b) \bmod 20 = (a \bmod 20) +(b \bmod 20)\)
Counterexample: The statement is false, because for the integer \(a=\) we have \((a+ 5) \bmod 20 \ne (a \bmod 20) +( 5 \bmod 20)\text{.}\)
(3)
select
The statement is true
The statement is false
For all integers \(a\) and all \(b\) we have \((a+ b) \bmod 6 = a +b\)
Counterexample: The statement is false, because for the integer \(a=\) we have \((a+ 3) \bmod 6 \ne a+ 3\text{.}\)
SubsectionApplying the properties of \(\fmod\)
Theorem 3.46 and Theorem 3.50 are particularly useful when computing \(\fmod\) with larger numbers.
Example3.52.Multiplication with and without Theorem 3.50.
which is longer but easier to compute, since we can easily find \(20\fmod 7\) and \(10\fmod 7\text{.}\)
Example3.53.Applying Theorem 3.46 and Theorem 3.50.
We compute \((61+(9\cdot 12))\fmod 7\text{.}\) We first evaluate the inner parenthesis and then the outer parenthesis. By Theorem 3.46 and Theorem 3.50 we have
In Checkpoint 3.55 apply properties the properties of \(\fmod\) to conduct computations modulo a given integer, when the values are only known modulo that integer.
Checkpoint3.55.Apply properties of \(\fmod\).
Let \(a\) be an integer.
Suppose that the remainder when \(a\) is divided by \(6\) is \(0\) and the remainder when \(b\) is divided by \(6\) is \(2\text{.}\)
That is, \(a\text{ mod } 6 = 0\) and \(b\text{ mod } 6 = 2.\)
Find:
\((a + a)\text{ mod } 6\) =
\((a+b)\text{ mod } 6\) =
\((a\cdot b)\text{ mod } 6\) =
\((a+5)\text{ mod } 6\) =
\((5\cdot b)\text{ 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.
