As mentioned in the Prelab section, it is possible to do arithmetic with congruence classes. To add two congruence classes modulo n, we just select any element a from the first class and any element b from the second class, and then compute a + b as we would for normal integers. The sum of the two congruence classes is then defined to be equal to the congruence class containing the "usual" sum a + b. For example, here are the congruence classes modulo 9:
Suppose that we wish to add the congruence class containing 3 to the congruence class containing 52. According to the recipe described above, we just select an element from each class, add them together, and see which class the resulting sum is in. Clearly 3 and 52 are elements of our classes, so let's try them first:
As we can see, the sum is in the congruence class containing 55, which corresponds to the second row above. To simplify discussions involving congruence classes, it is helpful to specify the congruence classes by identifying them with the unique integer from the set {0, 1, 2, . . . , n – 1} contained in a given class. Of course, from your work in the previous section, you know that the correct integer is equal to a % n, where a is any element of the congruence class. The on-line calculator can be used as shown to determine the congruence class in this way:
Things are fine so far, but suppose that we selected elements other than 3 and 52 from their respective congruence classes? After all, the recipe for addition says that we can use any elements from each class to do the addition. Will this work? Let's try some examples. From our table above, we can see that –15 and 66 are in the same class as 3 and that 7 and 79 are in the same class as 52. (In the terminology introduced in the Prelab section: "–15 and 66 are congruent to 3 mod 9" and "7 and 79 are congruent to 52 mod 9.") Here are the computations with 3 replaced by –15 and 66 and 52 replaced by 7 and 79:
Below is an applet that will check a bunch of choices from each congruence class at the same time:
This looks promising. For every selection we have made, the sum lands in the same congruence class. These examples illustrate the principle that addition of congruence classes is well defined.
Multiplication of congruence classes behaves in a similar manner. The recipe for multiplication is similar to that for addition: to multiply two congruence classes, we select any elements a and b from each of the classes and multiply them together. The product of the congruence classes is then defined to be the congruence class containing the product ab. We modify the above examples to illustrate multiplication of congruence classes.
Try some other examples, and when you feel comfortable with what is going on, move on to the research question and formalize your observations.
Research Question 2State and prove a theorem which shows that arithmetic of congruence classes modulo n is well defined. |
We now know that the arithmetic of congruence classes is well defined. You may be thinking, "So what? What's in it for me?" A reasonable question. A significant part of this course involves studying the arithmetic of congruences, and the ability to use any member of a congruence class to perform computations can frequently be a big help. Here's an example that isn't too exciting, but does illustrate the point. Suppose that you wish to find the value of n % 23894857635998476, where
(Remember, we said this wouldn't be exciting. We'll get to the cool examples soon enough.) One way to proceed would be to do the exponentiation, divide by 23894857635998476, and find the remainder. This will work in principle, but is not at all practical (n has over 74,000 digits.) A much faster way to go is to observe that
–1 (mod 23894857635998476),
so that
(–1)4578 (mod 23894857635998476),
It's easy to see that (–1)4578 = 1, and hence
1 (mod 23894857635998476),
Wasn't that much easier?
We close this section with a comment on the implications of what we have just seen. In moving from the set of integers to congruences modulo n, we go from an infinite set to a set with just n elements, the n congruence classes. Concretely, we can think of the n congruence classes as being represented by the possible remainders for division by n: 0, 1, . . ., n – 1. We can do addition, subtraction, and multiplication with this set. Since arithmetic for these operations is well defined for congruences, we can be somewhat lax about where we reduce to remainders modulo n. Moreover, if we are judicious in choosing when to reduce modulo n, we can do some interesting things as we will see in upcoming chapters.