Section 6.1 Adding in Circles
Motivating Questions.
In this section, we will explore the following questions.
What is congruence modulo \(m\text{?}\)
How can we do arithemtic modulo \(m\text{?}\)
What are some real-world examples of congruence?
This topic comes to us from the realm of mathematics known as number theory, which is all about the properties of the integers: positive whole numbers, negatives of whole numbers, and zero. Number theory is one of the oldest branches of mathematics; some of its hallmark theorems, still vital and taught today, have been known for thousands of years. And many of the deep structural features of the integers have found modern application in the hiding and transmitting of information. It is toward this last application that we now turn.
First, however, we need to be reminded of a suprisingly important result from school mathematics. We begin with some warmup questions.
Warmup 6.1.1.
For each pair of positive integers given below, perform long division to divide the first number by the second.
42, 6
42, 8
71, 9
0, 17
9, 71
8675309, 627
The Division Algorithm.
Let
\(a\) and
\(m\) be integers, with
\(m\gt 0\text{.}\) Then there exist unique integers
\(q,r\text{,}\) \(0\le r \lt m\text{,}\) such that
\begin{equation*}
a = m\cdot q + r.
\end{equation*}
We call
\(a\) the
dividend,
\(m\) the
divisor,
\(q\) the
quotient, and
\(r\) the
remainder.
Activity 6.1.2.
For each long division problem from
Warmup 6.1.1, identify the dividend, divisor, quotient, and remainder as described in
the Division Algorithm. What do you notice? What do you wonder?
Discussion 6.1.3.
What is meant by the word “unique” in
the Division Algorithm? Or, put slightly differently, when dividing 71 by 9, why do you think we do we not give a quotient of 6 and remainder of 17?
Of primary importance for us will be a consideration of the remainders obtained by dividing by a fixed positive integer \(m\gt 1\text{.}\)
Activity 6.1.4.
Throughout this activity, we will be dividing by \(m = 5\text{.}\) However, you should be thinking about how the answers might differ if we divide by a different integer \(m\text{.}\)
What remainders do you obtain when dividing the integers \(12, 16, 20, 24, 33\) by 5?
What remainders do you obtain when dividing the integers \(39, 52, 80, 108, 166\) by 5?
What remainders are possible upon division by 5? How do you know?
What remainders do you expect to be possible upon division by 103? How do you know?
For each of the five integers from the first question, find the integer from the second question whose remainder upon division by 5 is the same and write the pairs in a list.
For each pair in the list you made in the previous question, find the difference between the two integers and divide that number by \(m=5\text{.}\) What do you notice? What do you wonder?
The work you did in
Activity 6.1.4 provides motivation for the following definition.
Definition 6.1.5.
Let \(a,b\) be integers and \(m \gt 1\) an integer. We say that \(a\) and \(b\) are congruent modulo \(m\) if \(a\) and \(b\) have the same remainder upon division by \(m\text{.}\) In this case, we write \(a\equiv b\mod m\) and call \(m\) the modulus.
Equivalently, we say \(a\) and \(b\) are congruent modulo \(m\) if \(m\) evenly divides \(b-a\text{.}\)
Let’s explore this definition a bit more.
Activity 6.1.6.
For the given values below, determine whether \(a \equiv b\mod m\text{.}\)
\(a = 71\text{,}\) \(b = 39\text{,}\) \(m= 16\)
\(a = 17\text{,}\) \(b = 19\text{,}\) \(m = 4\)
\(a = 832\text{,}\) \(b = 584\text{,}\) \(m= 31\)
Congruence modulo \(m\) possesses several important properties. We highlight three of them in the following theorem.
Theorem 6.1.7.
Let \(m\gt 1\) be an integer, and suppose \(a,b,c\) are integers.
Congruence is reflexive: \(a\equiv a\mod m\)
Congruence is symmetric: If \(a\equiv b\mod m\text{,}\) then \(b\equiv a\mod m\text{.}\)
Congruence is transitive: If \(a\equiv b\mod m\) and \(b\equiv c\mod m\text{,}\) then \(a\equiv c\mod m\text{.}\)
Now that we are a bit more familiar with the definition, let’s test its limits.
Exploration 6.1.8.
Choose two different values of \(m\text{,}\) and for each value you choose, find two values of \(a\) and \(b\) so that \(a\equiv b\mod m\text{.}\)
Now choose a third integer \(c\text{.}\) For the integers you chose, is it true that \(a+c \equiv b+c\mod m\text{?}\) Is it true that \(a-c \equiv b-c\mod m\text{?}\) What about \(a\cdot c\equiv b\cdot c\mod m\text{?}\)
For each integer \(c\) you chose, find an integer \(d\) such that \(c\equiv d\mod m\text{.}\) Is it true that \(a+c \equiv b+d\mod m\text{?}\) Is it true that \(a-c \equiv b-d\mod m\text{?}\) What about \(a\cdot c \equiv b\cdot d\mod m\text{?}\)
Finally, note that \(5\cdot 2 \equiv 3\cdot 2\mod 4\text{.}\) Does it follow that \(5\equiv 3\mod 4\text{?}\)
Our discoveries in
Exploration 6.1.8 delineate the operations known as
modular arithmetic: we may add, subtract, and multipy integers mod
\(m\text{,}\) but we may not divide.
Activity 6.1.9.
Find the smallest nonnegative integer \(x\) satisfying:
\(\displaystyle x\equiv 9\cdot 4\mod 5\)
\(\displaystyle x\equiv 103+405\mod 10\)
\(\displaystyle x \equiv 56 + 6\mod 7\)
\(\displaystyle x \equiv 9\cdot 99\mod 5\)
Questions.
Consider the following questions, and what they have to do with modular arithmetic.
What day of the week will it be 62 days from now?
What month will it be 40 months from now?
What time will it be 27 hours from now?
In this section, we explored the notion of congruence modulo \(m\). We saw that we can reduce any integer \(x\) to its remainder upon division by \(m\text{,}\) and then do arithemtic operations of addition, subtraction, and multiplication mod \(m\text{.}\) This corresponds to natural cyclical process, such as times and dates.
In the next section, we’ll see how modular arithmetic can be used to reliably transmit information.
Exercises Exercises
1.
Find all solutions to the congruence \(6 + x \equiv 5\mod 15\text{.}\)
2.
Find all solutions to the congruence \(6x \equiv 5\mod 15\text{.}\)
3.
Let \(m\gt 1\) be an integer and let \(a\) be any integer. Explain why \(a\) is divisible by \(m\) if and only if \(a\equiv 0\mod m\text{.}\)
4.
Recall that the decimal representation of a number is a sum of powers of 10; for instance, \(6429 = 6\cdot 10^3 + 4\cdot 10^2 + 2\cdot 10 + 9\cdot 1\text{.}\)
Reduce \(10\mod 3\) and \(10^2 \equiv 100\mod 3\text{.}\)
What do you think it the smallest whole number \(x\) satisfying \(x\equiv 10^k\mod 3\) for any positive integer power \(k\text{?}\)
Explain why \(6429 \equiv 6 + 4 + 2 + 9 \mod 3\text{.}\)
Use your answers to these questions and
Exercise 6.1.3 to guess a way to determine if a number is divisible by 3. Explain your thinking.
