Modulo Operator Properties
Suppose we have a clock with only \(6\) “hours” on it’s face, and that at the usual \(12\)-o’clock position we have a \(0\). If I start at \(2\)-o’clock, and then add \(8\) hours, where do I end up on the clock?
Answer: \(4\)-o’clock. To get this answer, I loop around the clock once (passing through 6 hours, getting back to the starting point \(4\)), then adding 2 more hours for the full 8 hours.
Notice that the same result would happen if I added \(14\) hours or \(20\) hours. In the \(14\)-hour case, I’d loop around the clock twice before landing on \(4\). In the \(20\)-hour case, I’d loop around three times.
Notice also that I could have just as easily added only 2 hours from the start point if I wanted to land on \(4\), avoiding looping around at all. That is, if I started at \(2\) and added, say \(14\) hours, that is the same thing (i.e. has the same result) as adding just \(2\) hours; similarly for adding \(20\) hours.
Representing the first addition with modular arithmetic:
$$(2+14)\ mod\ 6=(2\ mod\ 6)+(14\ mod\ 6)=2+2=4$$
What this means is starting on hour \(2\) and then adding \(14\) hours is the same as adding \(14\ mod\ 6=2\) hours (accounting for the two loops around the clock).
This is just one relatively visual example of one arithmetical property of the modulo operator. The properties are summarized below.
Let \(n,m\) and \(k\) be integers. Then \((n\pm m)\ mod\ k=((n\ mod\ k)\pm (m\ mod\ k))\ mod\ k\).
Adding (or subtracting) two integers, mod \(k\) is the same as first finding each term, mod \(k\), then adding (or subtracting) the results, taking the modulus of the result.
$$\begin{align}(12+18)\ mod\ 5& =((12\ mod\ 5)+(18\ mod\ 5))\ mod\ 5\\ &=(2)+(3)\ mod\ 5\\ &= 5\ mod\ 5\\&=0\end{align}$$
Note that this is the same as if you instead added \(12+18\) first, then took modulus. Notice \((12+18)\ mod\ 5=30\ mod\ 5=0\).
Let \(n,m\) and \(k\) be integers. Then \((n\pm m)\ mod\ k=((n\ mod\ k)\pm (m\ mod\ k))\ mod\ k\).
Multiplying two integers, mod \(k\) is the same as first finding each term, mod \(k\), then multiplying the results, taking the modulus of the result.
$$\begin{align}(12\cdot 18)\ mod\ 5& =((12\ mod\ 5)\cdot (18\ mod\ 5))\ mod\ 5\\ &=(2)\cdot (3)\ mod\ 5\\ &= 6\ mod\ 5\\&=1 \end{align}$$
Notice that this is the same as if you multiplied first, then took the modulus. That is, \((12\cdot 18)\ mod\ 5=216\ mod\ 5=1\). “Taking modulus early” is usually easier than computing the modulus a large number that resulted from multiplication of big numbers.
Let \(n\) and \(m\) be integers. Then, \(n^x\ mod\ m=(n\ mod\ m)^x\ mod\ m\) for any positive integer \(x\).
If taking the modulus of a power of an integer, one can take the modulus of the base before calculating the power, and get the final result by taking modulus of the result of that power calculation.
$$\begin{align} 5^4\ mod\ 3&=(5\ mod\ 3)^4\ mod\ 3\\ &=(2)^4\ mod\ 3\\&= 16\ mod\ 3\\&=1\end{align}$$
\((123+142)\ mod\ 2=1\)
$$\begin{align}(123+142)\ mod\ 2&= ((123\ mod\ 2)+(142\ mod\ 2))\ mod\ 2\\&=(1)+(0)\mod\ 2\\&=1\ mod\ 2\\&=1\end{align}$$
\((42-135)\ mod\ 15=12\)
$$\begin{align}(42-135)\ mod\ 15&=((42\ mod\ 15)-(135\ mod\ 15))\ mod\ 15\\&= (12)-(0)\ mod\ 15\\&=12\end{align}$$
\((11+23+53+5178)\ mod\ 10=5\)
$$\begin{align}(11+23+53+5178)\ mod\ 10&=((11\ mod\ 10)+(23\ mod\ 10)+(53\ mod\ 10)+(5178\ mod\ 10))\ mod\ 10\\&=(1)+(3)+(3)+(8)\ mod\ 10\\&=15\ mod\ 10\\&=5\end{align}$$
\((23\cdot 123)\ mod\ 4=1\)
$$\begin{align}(23\cdot 123)\ mod\ 4&= ((23\ mod\ 4)\cdot (123\ mod\ 4)\mod 4\\&= (3)\cdot(3)\ mod\ 4\\&=9\ mod\ 4\\&=1\end{align}$$
\(21\cdot 22\cdot 23\ mod\ 2=0\)
$$\begin{align}21\cdot 22\cdot 23\ mod\ 2&=(21\ mod\ 2)\cdot(22\ mod\ 2)\cdot(23\ mod\ 2)\ mod\ 2\\&=(1)\cdot(0)\cdot(1)\ mod\ 2\\&=0\ mod\ 2\\&=0\end{align}$$
\((423)^{50}\ mod\ 3=0\)
$$\begin{align} (423)^{50}\ mod\ 3&=(423\ mod\ 3)^{50}\ mod\ 3\\&= (0)^{50}\ mod\ 3\\&= 0\ mod\ 3\\&=0\end{align}$$
\((32)^{10}\ mod\ 3=1\)
$$\begin{align} (32)^{10}\ mod\ 3&=(32\ mod\ 3)^{10}\ mod\ 3\\&= (2)^{10}\ mod\ 3\\&= (2^2)^5\ mod\ 3\\&=(4)^5\ mod\ 3\\&=(4\ mod\ 3)^5\ mod\ 3\\&=(1)^5\ mod\ 3\\&=1\ mod\ 3\\&=1\end{align}$$
\(1\). Yes. \(1\).
Note that one can find the \(1\)’s digit of any number by finding the remainder of dividing that number by \(10\). For example, suppose we have the number \(1243\). The \(1\)’s digit is \(3\). If we divide this number by \(10\) and take the remainder (that is, find \(1243\ mod\ 10\)), we will get that \(3\).
Now, applying this idea to the power \((11)^{30}\), using the power rule established above, we see that the \(1\)’s digit can be found by taking the number mod \(10\). Thus,
$$\begin{align} (11)^{30}\ mod\ 10&=(11\ mod\ 10)^{30}\ mod\ 10\\&= (1)^{30}\ mod\ 10\\&=1\ mod\ 10\\&=1\end{align}$$.
Thus, by the above, the \(1\)’s digit is \(1\) because we found the remainder of dividing our number \((11)^{30}\) by \(10\).