Skip to main content

Section 4.3 Excursion: Modular Arithmetic

Many applications of number theory use a new number system based on remainders (\(\fn{mod}\)), which we introduce in this section.

Subsection 4.3.A Not Last Game

In this puzzle, we introduce a game. To play the game, you will need an opponent (another person) and a pile of small objects such as coins, poker chips, candies, dried beans, etc.

Activity 4.3.A Not Last Puzzle.

The Not Last game starts with a pile of coins and two players, A and B. Player A removes one or two coins, their choice. Then player B removes one or two coins, their choice. Then A goes again and then B. They continue alternating until all the coins have been removed. At each turn each player must remove one or two coins. Whoever takes the last coin loses (misère) and, thus, each player’s goal is to be “not last”.
For example, suppose the game begins with a pile of seven coins. I, as the first player (A), remove two coins leaving a pile of five coins. My opponent (B) decides to remove only one coin, thus leaving a pile of four. I remove one more coin, leaving a pile of three. My opponent chuckles as she removes two coins, leaving me to remove the last coin. I lose.
We can summarize this series of moves in the diagram:
\begin{equation*} 7 \xrightarrow{A-2} 5 \xrightarrow{B-1} 4 \xrightarrow{A-1} 3 \xrightarrow{B-2} 1 \xrightarrow{A-1} 0 \text{ B wins } \end{equation*}
I wonder if there is a different strategy where I could win with seven coins. In general, for a pile of \(n\) coins, is there a strategy by which the first player (A) can definitely win? We assume, as is the custom, that both players are fully knowledgeable about the game, equally clever, and driven to win.
  1. Play four rounds of Not Last with seven coins to get a sense of the game and list the diagram for each.
  2. As we often do, let’s begin by looking at the smallest special cases. When \(n=1\) who wins: A or B? Explain and draw the diagram.
  3. When \(n=2\) is there a strategy for A to win? Explain and draw the diagram.
  4. Repeat for \(n=3\text{.}\)
  5. When \(n=4\text{,}\) there is no strategy A can use to win. Draw diagrams for each option (A takes one coin or A takes two coins) showing that B wins in either case.
  6. Before we try larger values of \(n\text{,}\) it is helpful to shift our perspective slightly. As we play the game with \(n\) coins, suppose there are eventually \(k\) coins left. For the purpose of this puzzle, \(k\) is a losing position if the player who goes next eventually loses and \(k\) is a winning position if the player who goes next eventually wins. Explain why \(k=1\) is a losing position, but \(k=2\) and \(k=3\) are winning positions.
  7. Let’s revisit the 4-coin game with this new perspective. If A takes one coin, then \(k=3\) which is a winning position and B goes next, so B wins. If A takes two coins instead, then \(k=2\) which is also a position number and B goes next, so B wins. We can draw the simpler diagram, using the \(\implies\) arrow to indicate a set of moves with known outcome.
    \begin{equation*} 4 \xrightarrow{A-1} 3 \implies \text{ B wins } \ \ \text{ OR } 4 \xrightarrow{A-2} 2 \implies \text{ B wins }\text{.} \end{equation*}
    We have just learned that \(k=4\) is a losing position. Find a strategy by which A wins when \(n = 5\text{.}\) Explain and draw the diagram. Hint: How can A leave B in a losing position?
  8. When \(n = 6\text{,}\) is there a strategy by which A wins? Explain and draw the diagram. Remember, A is trying to leave B in a losing position, and vice versa.
  9. When \(n = 7\text{,}\) is there a strategy by which A wins? Explain and draw the diagram.
  10. Make a table showing \(n=1,2,3,\ldots, 10\) in the top row and the winner (A or B) for each starting number of \(n\) coins in the bottom row. Be sure you check that the answer is correct for yourself, but you are not expected to explain your reasoning here.
  11. Who do you think wins if the game starts with \(n = 100\) coins? Is \(k=100\) a winning position or a losing position?

Subsection 4.3.B The Mod Clock

There is a way to visualize the remainder of \(a\) \(\fn{mod}\) \(n\text{.}\)

Remark 4.3.2 Mod Clock.

To find \(a\) \(\fn{mod}\) \(n\) when \(n \ge 1\text{,}\) imagine an \(n\) hour “clock” with hours marked \(0, 1, 2, \ldots, n-1\) hours. To find the value of \(a\) \(\bs{mod}\) \(n\) when \(a\) is positive, we count \(a\) hours clockwise from \(0\text{.}\) For example, the \(\bs{mod}\) 12 is shown in Figure 4.3.3 and the \(mod\) 5 clock is shown in Figure 4.3.3 The end mark is \(a\) \(\bs{mod}\) \(n\text{.}\) When \(a\) is negative, we instead count counterclockwise.
Figure 4.3.3. The 12-hour clock
Figure 4.3.4. The 5-hour clock

Example 4.3.5 Evaluating \(\fn{mod}\) using the Mod Clock.

 
  1. Use the 12-hour clock (marked \(0,1, \ldots, 11\) instead of the usual \(1,2, \ldots 12\)) shown in Figure 4.3.3 to calculate 20 \(\fn{mod}\) 12.
    Solution.
    We start at 0 and count clockwise 20 hours:
    \begin{equation*} 1,2,3,4,5,6,7,8,9,10, 11,0,1,2,3,4,5,6,7,8\text{.} \end{equation*}
    Thus 20 \(\fn{mod}\) 12 = 8.
  2. Use the 5-hour clock shown in Figure 4.3.4 to calculate 67 \(\fn{mod}\) 5.
    Solution.
    Instead of counting off 67 hours, note that 50 hours will take us around the clock 10 times, ending at 0. That leaves us \(67-50-17\) hours to count from there. Note that \(15 = 3 \times 5\text{,}\) so 15 hours will take us around the clock 3 times, ending at 0. That leaves us \(17-15 = 2\) hours to count from there, which ends at 2. Thus, 67 \(\fn{mod}\) 5 = 2.
  3. Use the 5-hour clock shown in Figure 4.3.4 to calculate -12 \(\fn{mod}\) 5.
    Solution.
    Since -12 is negative, we start at 0 count counterclockwise 12 hours:
    \begin{equation*} 4,3,2,1,0,4,3,2,1,0,4,3\text{.} \end{equation*}
    Thus, \(-12\) \(\fn{mod}\) 5 = 3.
Practice working with the mod clock.

Activity 4.3.B The Mod Clock.

 
  1. Draw the 12-hour clock and use it to evaluate 17 \(\fn{mod}\) 12, 127 \(\fn{mod}\) 12, 4 \(\fn{mod}\) 12, and -2 \(\fn{mod}\) 12.
  2. Draw the 5-hour clock and use it to evaluate 17 \(\fn{mod}\) 5, 127 \(\fn{mod}\) 5, 4 \(\fn{mod}\) 5, and -2 \(\fn{mod}\) 5.

Subsection 4.3.C The Integers mod \(n\)

We can now define the integers mod \(n\text{.}\)

Definition 4.3.7 The integers mod \(n\).

 
  1. For a positive integer \(n\text{,}\) the integers mod \(n\text{,}\) denoted \(\mathbb{Z}_n\) and pronounced “Z mod \(n\)”, is the set
    \begin{equation*} \mathbb{Z}_n = \{0, 1, 2,\ldots, n-1\}\text{.} \end{equation*}
    For example,
    \begin{equation*} \mathbb{Z}_5 = \{0,1,2,3,4\} \end{equation*}
    and
    \begin{equation*} \mathbb{Z}_{12} = \{0,1,2,3,4,5,6,7,8,9,10,11\}\text{.} \end{equation*}
  2. We can define addition \(\oplus\) and multiplication \(\otimes\) on \(\mathbb{Z}_n\) as follows:
    \begin{equation*} a \oplus b = (a+b)~\fn{mod}~n \end{equation*}
    \begin{equation*} a \otimes b = (ab)~\fn{mod}~n \end{equation*}
    For example, in \(\mathbb{Z}_{10}\) , we have
    \begin{equation*} 5 \oplus 7 = 12~\fn{mod}~10 = 2\text{,} \end{equation*}
    \begin{equation*} 5 \otimes 7 = 35~\fn{mod}~10 = 5\text{,} \end{equation*}
    and
    \begin{equation*} 4^2 = 4 \otimes 4 = 16 ~\fn{mod}~10 = 6\text{.} \end{equation*}
  3. As in the usual order of operations (PEMDAS, Definition 2.1.20), multiplication (\(\otimes\)) is higher priority than addition (\(\oplus\)).
  4. Addition and multiplication satisfy the commutative property
    \begin{equation*} a \oplus b = b \oplus a \text{ and } a \otimes b = b \otimes a\text{,} \end{equation*}
    the associative property
    \begin{equation*} (a \oplus b) \oplus c = a \oplus (b \oplus c) \text{ and } (a \otimes b) \otimes c = a \otimes (b \otimes c)\text{,} \end{equation*}
    and the distributive property
    \begin{equation*} a \otimes (b \oplus c) = (a \otimes b) \oplus (a \otimes c)\text{.} \end{equation*}
We can write arithmetic tables for \(\mathbb{Z}_n\text{.}\)

Example 4.3.8 Addition and multiplication tables for \(\mathbb{Z}_4\).

 
  1. Write the addition and multiplication tables for \(\mathbb{Z}_4\text{.}\)
    Solution.
    Table 4.3.9 shows the tables. For example,
    \begin{equation*} 1 \oplus 3 = 4~\fn{mod}~4 = 0 \end{equation*}
    and
    \begin{equation*} 2\otimes 3 = 6~\fn{mod}~4 = 2\text{.} \end{equation*}
    Table 4.3.9. The arithmetic tables for \(\mathbb{Z}_4\text{,}\) the integers mod 4
    \(\oplus\) 0 1 2 3
    0 0 1 2 3
    1 1 2 3 0
    2 2 3 0 1
    3 3 0 1 2
    		      
    \(\otimes\) 0 1 2 3
    0 0 0 0 0
    1 0 1 2 3
    2 0 2 0 2
    3 0 3 2 1
  2. True or false? If \(a \otimes b = 0\) in \(\mathbb{Z}_4\text{,}\) then \(a = 0\) or \(b = 0\text{.}\)
    Solution.
    The question is asking if there are any 0s in the multiplication table other than in the row and column headed by 0. It turns out there are and so this statement is false. As a counterexample, \(2 \neq 0\text{,}\) but \(2 \otimes 2 = 4~\fn{mod}~4= 0\) in \(\mathbb{Z}_4\text{.}\)
  3. For which values of \(a \in \mathbb{Z}_{4}\text{,}\) does \(a \otimes x = 1\) have a solution?
    Solution.
    The question is asking which rows in the multiplication table have a one in them? The rows headed by 1 and 3 each have a 1 because \(1 \otimes 1 = 1\) and also \(3 \otimes 3 = 1\text{.}\) The answer is \(a = 1, 3\text{.}\) (It is coincidence that the corresponding solutions are \(x=1, 3\text{.}\))
It is your turn to work with arithmetic in the integers mod \(n\text{.}\)

Activity 4.3.C Arithmetic mod \(n\).

 
  1. In \(\mathbb{Z}_5\) confirm that \(2 \oplus 4 = 1\) and \(2 \otimes 4 = 3\text{.}\)
  2. In \(\mathbb{Z}_6\) confirm that \(2 \oplus 4 = 0\) and \(2 \otimes 4 = 2\text{.}\)
  3. Write the addition and multiplication tables for \(\mathbb{Z}_5\) and \(\mathbb{Z}_6\text{.}\) Hint: If you are working with a partner, then one of you should do \(\mathbb{Z}_5\) while the other does \(\mathbb{Z}_6\text{,}\) just check each other’s work. We need these tables for later parts of this activity.
  4. True or false? If \(a \otimes b = 0\) in \(\mathbb{Z}_6\text{,}\) then \(a = 0\) or \(b = 0\text{.}\) What about in \(\mathbb{Z}_5\text{?}\)
  5. For which values of \(a \in \mathbb{Z}_{5}\text{,}\) does \(a \otimes x = 1\) have a solution? What about in \(\mathbb{Z}_6\text{?}\)

Subsection 4.3.D Exercises

Subsubsection Exercises for 4.3.A Not Last Game

1. Practice.

This exercise refers to the Not Last game introduced in Activity 4.3.A. We know that one and four are losing positions, whereas two and three are winning positions.
  1. Explain why five is a winning position.
  2. Explain why six is a winning position.
  3. Explain why seven is a losing position.
Check.
  1. Take one to leave your opponent with four, which is a losing position.
  2. Hint: You want to leave your opponent in four again.
  3. Hint: Consider the two cases where one or two is taken.

2. Understand.

This exercise refers to the Not Last game introduced in Activity 4.3.A.
  1. Which integers \(n\) are a losing position? State your answer as a conjecture. Hint: Use \(\fn{mod}\) in your answer.
  2. Suppose that you are in a winning position \(n\) while playing the Not Last game introduced in Activity 4.3.A. What is your strategy for deciding whether to take one or two coins? Be specific. Hint: Your answer should involve \(n\) and use \(\fn{mod}\text{.}\)
Check.
  1. Hint: Your answer depends on \(\fn{mod}\) 3.
  2. Hint: Look at \(n \fn{ mod } 3\) and break down your answer into cases.

3. Explore.

In this exercise we define a new game, Half, which starts with a pile of coins and two players, A and B. Player A goes first and then A and B take turns removing coins from the pile. The rule is that at each turn, a player must remove at least one coin and at most half of the coins, with the exception that if there is one coin left, then they must take it. For example, if there are six or seven coins, the next player can take one, two, or three coins. As in the Not Last game, whoever takes the last coin loses the Half game.
  1. Who wins the Half game when \(n=1,2,3\text{,}\) the first player (A) or the second player (B)? Explain.
  2. Who wins the Half game when \(n=4,5,6,7\text{?}\) Explain.

4. Explore.

This exercise refers to the Half game introduced in Exercise 3. Complete Exercise 3 before trying this exercise.
  1. Which integers \(n\) are a losing position in the Half game? State your answer as a conjecture.
  2. Suppose that you are in a winning position \(n\) while playing Half. What is your strategy for deciding how many coins to take? Hint: your answer should involve \(n\text{.}\)

Subsubsection Exercises for 4.3.B The Mod Clock

5. Practice.

In each part of this exercise, draw the relevant mod clock and show how to use it to evaluate the quantity. Recall that we rotate clockwise for positive integers.
  1. 23 \(\fn{mod}\) 5. Hint: Copy the mod 5 clock from Figure 4.3.4.
  2. 23 \(\fn{mod}\) 12. Hint: Copy the mod 12 clock from Figure 4.3.3.
  3. 23 \(\fn{mod}\) 10. Hint: The mod 10 clock has labels \(0,1,2,3,4,5,6,7,8,9\text{.}\)
  4. 23 \(\fn{mod}\) 6. Hint: The mod 6 clock has labels \(0,1,2,3,4,5\text{.}\)
Check.
The answers in some order are zero, one, three, and five.

6. Understand.

In each part of this exercise, draw the relevant mod clock and show how to use it to evaluate the quantity. Recall that we rotate counterclockwise for negative integers.
  1. \(-10\) \(\fn{mod}\) 5
  2. \(-10\) \(\fn{mod}\) 6
  3. \(-10\) \(\fn{mod}\) 12
  4. \(-10\) \(\fn{mod}\) 3
Check.
The answers to each part are zero or two.

7. Recap.

Do you know …
  1. How to calculate \(a~\fn{mod}~n\) using a “mod clock”? Make sure your answer includes both positive and negative numbers \(a\text{.}\)
  2. What values of \(a\) have \(a~\fn{mod}~n=0\text{?}\) That is, which values of \(a\) end at 0 on the \(\fn{mod}\) \(n\) clock?

8. Explore.

 
  1. Use the idea of a mod \(n\) clock to explain why \(a\) \(\fn{mod}\) \(n=0\) whenever \(a\) is a multiple of \(n\text{.}\)
  2. Use the idea of a mod \(n\) clock to explain why \(-1\) \(\fn{mod}\) \(n=n-1\) and \(-2\) \(\fn{mod}\) \(n=n-2\text{.}\) Hint: The mod \(n\) clock has labels \(0,1,2,\ldots,n-1\text{.}\)

Subsubsection Exercises for 4.3.C The Integers mod \(n\)

9. Practice.

 
  1. Write out the addition and multiplication tables for \(\mathbb{Z}_3=\{0,1,2\}\text{.}\) Hint: Each entry in your tables should be 0, 1, or 2.
  2. Write out the addition and multiplication tables for \(\mathbb{Z}_2=\{0,1\}\text{.}\) Hint: Each entry in your tables should be 0 or 1.
Check.
  1. Hint: Check that \(2 \oplus 2 = 1\) and \(2 \otimes 2 = 1\text{.}\)
  2. Hint: The only unusual entry is \(1 \oplus 1 = 0\text{.}\)

10. Practice.

This exercise repeats Activity 4.3.C (c).
  1. Write out the arithmetic tables for \(\mathbb{Z}_5\text{.}\)
  2. Write out the arithmetic tables for \(\mathbb{Z}_6\text{.}\)
Check.
  1. Hint: The rows for two are \(2,4,1,3,0\) and \(0,2,4,3,1\text{.}\)
  2. Hint: The rows for two are \(2,4,0,2,4,0\) and \(0,2,4,0,2,4\text{.}\)

11. Understand.

For each equation, find every solution \(\mathbb{Z}_n\text{,}\) if any, by checking each element of \(\mathbb{Z}_n\) to see if it is a solution.
  1. Solve \(x \oplus 4 = 1\) in \(\mathbb{Z}_5\text{.}\)
  2. Solve \(x \oplus 4 = 1\) in \(\mathbb{Z}_6\text{.}\)
  3. Solve \(2 \otimes x = 3\) in \(\mathbb{Z}_5\text{.}\)
  4. Solve \(2 \otimes x = 3\) in \(\mathbb{Z}_6\text{.}\)
  5. Solve \(3 \otimes x \oplus 1 = 3\) in \(\mathbb{Z}_5\text{.}\) Note that the usual order of operations applies, so this equation means \((3 \otimes x) \oplus 1 = 3\)
Check.
  1. \(\displaystyle x=2\)
  2. Hint: There is one solution.
  3. \(\displaystyle x=4\)
  4. Hint: Look at the row for two in the multiplication table. Explain why there is no solution.

12. Understand.

In \(\mathbb{Z}_n\text{,}\) we write \(x^2=x \otimes x\text{.}\)
  1. In \(\mathbb{Z}_5\text{,}\) what are the solutions, if any, of \(x^2\oplus 1 = 0\text{?}\)
  2. In \(\mathbb{Z}_6\text{,}\) what are the solutions, if any, of \(x^2\oplus 1 = 0\text{?}\)
  3. In \(\mathbb{Z}_{10}\text{,}\) what are the solutions, if any, of \(x^2\oplus 1 = 0\text{?}\)
  4. In \(\mathbb{Z}_2\text{,}\) what are the solutions, if any, of \(x^2\oplus 1 = 0\text{?}\)
Check.
  1. Hint: Two of \(0,1,2,3,4\) are solutions. Check each one.
  2. Hint: There is no solution.
  3. Hint: One solution is \(x=3\text{.}\) There is a second solution.
  4. Hint: There is one solution.

13. Understand.

 
  1. Give an example of elements \(a\) and \(b\) in \(\mathbb{Z}_{10}\) where \(a \otimes b = 0\text{,}\) but \(a \neq 0\) and \(b \neq 0\text{.}\)
  2. Can you find elements \(a\) and \(b\) in \(\mathbb{Z}_5\) where \(a \otimes b = 0\text{,}\) but \(a \neq 0\) and \(b \neq 0\text{?}\) Explain.

14. Understand.

 
  1. For which values of \(a \in \mathbb{Z}_5\text{,}\) does \(a \otimes x = 1\) have a solution?
  2. For which values of \(a \in \mathbb{Z}_6\text{,}\) does \(a \otimes x = 1\) have a solution?
  3. For which values of \(a \in \mathbb{Z}_{10}\text{,}\) does \(a \otimes x = 1\) have a solution? You should be able to answer without writing the multiplication table.
  4. For which values of \(a \in \mathbb{Z}_8\text{,}\) does \(a \otimes x = 1\) have a solution? You should be able to answer without writing the multiplication table.
Check.
  1. \(\displaystyle a=1,2,3,4\)
  2. Hint: \(a=1\) and one more value. Look for ones in the multiplication table.
  3. Hint: There are four values of \(a\text{,}\) all odd.
  4. \(\displaystyle a=1,3,5,7\)

15. Recap.

Do you know …
  1. What \(\mathbb{Z}_n\) is?
  2. How to add and multiply in the integers mod \(n\text{?}\)
  3. How to construct the addition and multiplication tables mod \(n\text{.}\)
  4. How to solve equations in \(\mathbb{Z}_n\text{?}\)

16. Explore.

In \(\mathbb{Z}_n\text{,}\) we write \(2^k=\underbrace{2 \otimes 2 \otimes 2 \otimes \cdots \otimes 2}_{k \text{ times } }\text{.}\) On this exercise, you are welcome to use computational technology.
  1. In \(\mathbb{Z}_5\text{,}\) calculate \(2^1\text{,}\) \(2^2\text{,}\) \(2^3\text{,}\) \(2^4\text{,}\) \(2^5\text{,}\) \(2^6\text{,}\) \(2^7\text{,}\) and \(2^8\text{.}\)
  2. Based on the pattern in 16.(a), conjecture the value of \(2^{50}\text{.}\) Explain your reasoning.
  3. In \(\mathbb{Z}_6\text{,}\) calculate \(2^1\text{,}\) \(2^2\text{,}\) \(2^3\text{,}\) \(2^4\text{,}\) \(2^5\text{,}\) \(2^6\text{,}\) \(2^7\text{,}\) and \(2^8\text{.}\)
  4. Based on the pattern in 16.(c), conjecture the value of \(2^{50}\text{.}\)Explain your reasoning.
Check.
  1. Hint: The list begins \(2, 4, 3, \ldots\text{.}\)
  2. Hint: The list begins \(2,4,2,\ldots\text{.}\)

17. Explore.

  An element \(a\) of \(\mathbb{Z}_n\) is a zero divisor if \(a \neq 0\) but there is an element \(b\) of \(\mathbb{Z}_n\) with \(b \neq 0\) also, and yet \(ab = 0\text{.}\) That is, if there is more than one 0 in the row for \(a\) in the multiplication table for \(\mathbb{Z}_n\text{.}\) Exercise 13 asked for an example of a zero divisor in \(\mathbb{Z}_{10}\) and asked whether there were zero divisors in \(\mathbb{Z}_5\text{.}\) Conjecture which integers \(n\) have the property that \(\mathbb{Z}_n\) has zero divisors and which integers \(n\) have the property that \(\mathbb{Z}_n\) does not have zero divisors.
PrevTopNext