Tuesday 20 September class

Topics:
More modular arithmetic...

Activity: a more detailed version of the "odd/even/sometimes" activity from last week. We will be able to answer these questions completely using modular arithmetic (showing one application of it).

Continuing the discussion of modular arithmetic from last time:

Replacing (or better, representing) a number by its congruent residue is referred to as reducing that number. I will use that language when describing the operations below.

The modular residues for a particular modulus form a number system (technically, it's called  a ring) and since there is only a finite number of residues, we can write down complete addition and multiplication tables for all the numbers in that system. (This will be done next time.)

To add (or subtract) or multiply in these number systems, we can either reduce the numbers before we perform the operations, or perform the operations and then reduce. We saw and worked on examples which show this is true:
   In the reading, the problem of finding the units digit of a sum of four integers
    (and you can also look at the example following that one, which is of subtraction)
   We also found the product 57•93 (mod 5) in two ways: first, by multiplying and then reducing mod 5; second, by reducing mod 5 and then multiplying the residues (and then we had to reduce again). The two answers were the same (both were 1).

Another example from the reading: to find the last two digits of 7¹⁹⁴²
We computed some powers of 7 mod 100 (so the residues will be the tens and units digits) and saw that there was a pattern, that the residues mod 100 repeat the values 7, 49, 43, 1: and every time the exponent is a multiple of 4, the residue mod 100 is 1. It would be nice if our exponent 1942 were a multiple of 4, but it is not: it leaves a remainder of 2 when we divide 1942 by 4. (This means that 1942 can be expressed as 1940+2 where 1940 is a multiple of 4.) We then used that pattern to reduce 7¹⁹⁴⁰and 7² separately
We then observed that 7¹⁹⁴⁰•7² = 7¹⁹⁴² by a property of exponents. We then used that pattern we had found to reduce 7¹⁹⁴⁰and 7² separately, and so we could combine the two previous results to solve the problem. (See the reading for the details.)

Notice that in this exponentiation problem, we cannot just reduce the exponent mod 100 and then compute: it will not give the correct answer. But there is a pattern we can exploit (which actually involves mod 4 arithmetic!) and that will always be the case in this type of problem.

More on exponential expressions in modular arithmetic next time, with examples to show what does and does not work.


The operations that work well with modular arithmetic are: addition, subtraction (which is really just a version of addition, not a separate operation), multiplication, and whole number exponents (which is just repeated multiplication). Division is a problem because the result of dividing an integer by an integer may not be an integer, and we are only "allowed" to use integers in the modular arithmetic.

Homework:
The first thing to do is to go back over these examples (this time and last time) and the vocabulary/notation and make sure that you understand what we did in class. Use your Journal to write things out as necessary.

Problems to work:
1) Reduce (find the residues):
     57 ≡ ____ (mod 8)
     24 ≡ ____ (mod 6)
     3 ≡ ____ (mod 5)
     985,321 ≡ ____ (mod 1000)
2) Compute each of the following:
     56 + 113 (mod 5)
     918•46 (mod 11)
     5²⁴⁸⁷⁵⁶(mod 6)

Hint: that last one is surprisingly easy once you've found the pattern in the powers of 5 mod 6. Think about the problem in front of you, don't try to model it on anything else!

Next up: More examples, addition and multiplication tables for modular arithmetic, and later some applications of modular arithmetic: check digits for UPC, ISBN, and so forth, leading eventually to the RSA algorithm.