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 elementafrom the first class and any elementbfrom the second class, and then computea+bas 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" suma+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 toa%n, whereaisanyelement 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

anyelements 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

aandbfrom each of the classes and multiply them together. The product of the congruence classes is then defined to be the congruence class containing the productab.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 2

State and prove a theorem which shows that arithmetic of congruence classes modulo

nis 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, wheren= 23894857635998475^{4578}.(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 (

nhas over 74,000 digits.) A much faster way to go is to observe that23894857635998475 –1 (mod 23894857635998476), so that

23894857635998475 ^{4578}(–1)^{4578}(mod 23894857635998476),It's easy to see that (–1)

^{4578}= 1, and hence23894857635998475 ^{4578}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 justnelements, thencongruence classes. Concretely, we can think of thencongruence classes as being represented by the possible remainders for division byn: 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 modulon. Moreover, if we are judicious in choosing when to reduce modulon, we can do some interesting things as we will see in upcoming chapters.

Section 3.1 | Section 3.2 | Section 3.3 | Section 3.4

Copyright © 2001 by W. H. Freeman and Company