An Introduction to Modular Arithmetic - NUMBER THEORY - TWO PILLARS OF MATHEMATICS - Mathematics for the liberal arts

Mathematics for the liberal arts (2013)

Part II. TWO PILLARS OF MATHEMATICS

Chapter 5. NUMBER THEORY

5.12 An Introduction to Modular Arithmetic

Odds and Evens

The notion of the parity of a number, whether it is odd or even, is quite useful.

A Magic Trick. The magician takes a half-dozen or so coins, throws them on a table. She asks for a volunteer. Then she turns her back on the table and asks the volunteer to turn over two of the coins, any two. Then to turn two more, then two more. Then the volunteer should hide one coin with his hand. The magician turns back around, looks at the table, and announces whether the hidden coin is heads or tails. How does she do it?

The magician counts the number of heads before she looks away, and remembers whether it is odd or even. When the volunteer turns two coins, one of three things can happen. The two coins are both heads, in which case the number of heads increases by two; both tails, in which case the number of heads decreases by two; or one heads and one tails, in which case the number of heads stays the same. In all three cases, the parity of the number of heads is unchanged. So at the end, the magician still knows whether the number of heads is odd or even. She can then tell whether the hidden coin is heads or tails, to make the parity of total number of heads right.

Next is an 18th century classic.

The Bridges of Königsberg. In 1735 Leonhard Euler came across a puzzle based on the layout of the city of Königsberg in Prussia (now called Kaliningrad, in Russia). The city was located on the Pregel River, which had two islands. The two sides of the river and the islands were connected by bridges as in Figure 5.8.

The puzzle was this: design a tour, starting anywhere, that takes you across each bridge once and only once, and ends at the starting point.

Figure 5.8 The seven bridges of Königsberg.

images

Euler, being a mathematician, abstracted out the important features of the problem, ignoring others (such as the lengths of the bridges) that wouldn’t affect any solution. Using modem terms, he defined a graph, pictured in Figure 5.9. Each land mass—the two islands and the two sides of the river—is represented by a dot, called a vertex (plural vertices). Each bridge is represented by a line, called an edge, connecting its two land masses.

Figure 5.9 The bridges of Königsberg graph.

images

The puzzle then becomes this: starting at any vertex, traverse each edge once and only once, ending at the starting point. Of course, Euler didn’t just rephrase the problem, but solved it. In fact, he solved a more general problem, for any graph. He argued as follows. Suppose we start at some vertex A. When we leave A, we cross one of its edges. The first time we return to A, we have used two of its edges. If we return again, we will have used two more edges, for a total of four. In general, each time we return, we have used two more edges, so the total number of its edges used is even. Since we have to return at the end, we will then have used an even number of edges. But each vertex in our graph has an odd number of edges, so this is not possible. The puzzle has no solution.

Euler’s solution was even more general. Consider a vertex other than the starting vertex. Each time we enter and leave it, we use two edges. So at this vertex as well, we must use a total number of edges that is even. In other words, for any graph, in order for such a tour to exist, every vertex must have an even number of edges.

Euler published his solution in 1735. The general theorem is this: A graph has a solution if, and only if, every vertex has an even number of edges, and the graph is connected (you can get from any vertex to any other). Such a solution is now called an Eulerian path, in his honor. In fact, this theorem is considered the first in the area of graph theory, which has become a large and important topic of mathematical research and application in the last 50 years.

The Envelope Puzzle. Here is another classic puzzle, which you may have seen before. Starting anywhere, trace the shape in Figure 5.10, without repeating any line.

Figure 5.10 The envelope puzzle.

images

Do you see the connection to the last problem? Consider the graph in Figure 5.11.

Figure 5.11 The envelope graph.

images

This problem is a variation of the last one. We need to traverse every edge exactly once, but we aren’t obligated to start and end at the same vertex. By the argument we used above, every vertex except maybe the starting and ending vertices, must have an even number of edges. If you check the graph, you can see that exactly two vertices have an odd number of edges, the two at the bottom. So these two must be our starting and ending points. A solution is shown in Figure 5.12. The edges are traversed in the order given.

Opening and Closing Lockers. An army base has a cavernous room with a row of 1000 lockers, numbered 1 through 1000. A soldier walks down the row, opening every locker. A second soldier comes by and closes every second locker. Another either opens or closes every third locker, depending on whether it was closed or open before, and so on. The 1000th soldier either opens or closes the 1000th locker. Which lockers are now open?

Figure 5.12 A solution to the envelope puzzle.

images

It is easy to figure out which of the lockers 1-10 are open at the end. Only the first soldier touches the first locker, so it is open. The second locker is opened by the first soldier, closed by the second, and bypassed by the others, so it is closed. After you figure out the first 10 lockers, you may notice a pattern.

How do we solve this problem? (If you enjoy puzzles, you may want to try this one before reading our solution.) The first question we need to answer is this: how do we tell if soldier m changes (opens or closes) locker n? Notice that soldier 2 changes lockers 2, 4, 6, 8, … Soldier 3 changes lockers 3, 6, 9, … In general, soldier m changes locker n if m divides n. In other words, the number of times a locker is changed is the number of divisors it has.

A locker ends up closed if it is changed an even number of times, open if it is changed an odd number of times. So, locker n is open at the end if n has an odd number of divisors. Therefore, we can answer the question if we can tell which numbers have an odd number of divisors.

Consider the divisors of 12, for example: they are 1, 2, 3, 4, 6, and 12. Another way to list them: 1 and 12, 2 and 6, 3 and 4. The divisors are paired off, each pair multiplying to 12. Because of this pairing, it is easy to see that the number of divisors of 12 is even. If we try this with 9, however, we get 1 and 9, 3 and 3. Because 9 is a square, 3 is matched with itself, so there are really an odd number of divisors of 9. Do you see the pattern? If n is not a square, its divisors pair up, so there are an even number of divisors. If n is a square, one of the divisors pairs with itself, so there are an odd number of divisors. Combining this with the observation of the last paragraph, we have our solution: locker n is open if, and only if, n is a square.

Modular Arithmetic

Let’s look at odds and evens a bit more closely. Recall that every even number m can be written in the form m = 2k, and every odd number n can be written in the form n = 2k + 1.

How is parity affected when we do arithmetic on numbers? Suppose we add two even numbers m and n. We can write them as m = 2k and n = 2l. Then

images

Thus the sum of two even numbers is always even. How about two odds? Using our standard form for odds,

images

so the sum of two odds is even. As a final example, let us multiply an even and an odd number: (2k) (2l + 1) = 2[k(2l + 1)], so the product is even. One can go through all of the other cases; the general principle is this: if we know the parity of two numbers, we can determine the parity of their sum, difference, and product.

If we are concerned only about the parity of numbers, we can represent a number by a simple one that has the same parity. We can use 0 and 1. For instance, if we don’t remember the parity of the sum of two odd numbers, we simply consider 1 + 1. It is even, so every sum of two odds must be even.

This arithmetic, taking into account only the parity, is an example of modular arithmetic, with 2, in this case, being the modulus. (The formal definitions are in the next section.) We can summarize modular arithmetic with modulus 2 by the following tables, writing [0] to represent even numbers, and and [1] to represent odd numbers.

images

For example, the first table tells us that [1] + [0] = [1], in other words, that the sum of an odd number and an even number is odd.

There is another way to look at this arithmetic, using remainders upon division by 2. For example, let us look at [1] + [1]. According to our table, [1] + [1] = [0], which may strike you as strange. But if we think of the Is as numbers, 1 + 1 = 2, and 2 has remainder 0. You can check that this works for everything in the tables; if you do normal arithmetic, then take the remainder on division by 2, you get the results in the table.

In the following sections, we will pursue these ideas in a more general setting.

EXERCISES

5.64 Here is a variation on the magic trick at the start of the section. Have the volunteer pick a number from 1 to the number of coins, tell you the number, then turn that many coins. As before, one coin is covered. How would you figure out whether the hidden coin was heads or tails? (Hint: suppose that the volunteer turned three coins. What would happen? How about four coins?)

images

5.65 Starting anywhere, trace the figure below, without repeating any line.

5.66 What four odd integers add up to 19?

5.67 Produce tables for addition, subtraction, and multiplication, like those in this section, for modulus 3. (Hint: the possible remainders upon division by 3 are 0, 1, and 2.)

5.68 Modular arithmetic is sometimes called clock arithmetic, because twelve-hour clocks repeat in the same way. Construct the addition and multiplication tables for modular arithmetic with modulus 12.