Thursday 22 September class

Topics:
• Activity: computing 96³ mod 7  two ways:
  By first computing 96³ and then reducing mod 7
  By first reducing 96 mod 7, then raising that number to the 3rd power (and then reducing again)
This showed by example that we can reduce the base of a whole number exponent before exponentiation in modular arithmetic. (This is not a proof, but an example.)

While showing the solution on the board, I showed how you can use a calculator to find a remainder/residue. The details are in this post.

We contrast this with the computation of 7¹⁹⁴² mod 100 that we did last time. The difference was that there we would want to reduce the exponent, but reducing mod 100 does not work. (I could not show this directly because the numbers involved are too big, but I made an example of 3¹⁵ mod 5 later.)

This led to a discussion of a heuristic that connects to the thinking involved in the way we found the value of 7¹⁹⁴² mod 100. I have posted those notes separately.

Next  was to construct some addition and multiplication tables for modular arithmetic. Since the modular number systems are finite, we can construct complete tables for them. Fixing the modulus m,  we show all the residues for that modulus along the top and side of the table: then the entry at each intersection of a row and column is the sum or product of those two residues, reduced mod m. We made the following addition and multiplication tables:

Mod 2: Addition

+	0	1
0	0	1
1	1	0

Mod 2: Multiplication

•	0	1
0	0	0
1	0	1

Mod 3: Addition

+	0	1	2
0	0	1	2
1	1	2	0
2	2	0	1

The tables for mod 2 allow us to prove the results for the questions in last time's warmup, and others, since an integer is even if (and only if) it is congruent to 0 mod 2, and it is odd if (and only if) it is congruent to 1 mod 2. Therefore, for example, we can translate:

0+0 ≡ 0 (mod 2) means that "even plus even = even"

1+1 ≡ 0 (mod 2) means that "odd plus odd = even"

But we get even more: 0+1 ≡ 1 (mod 2) means that "even plus odd = odd"

Go through the tables and see what else they prove!


Homework:
• Journal assignment: Write about the group activity (computing 96³ (mod 7) two ways): what your group did, and what you learned about modular arithmetic from this.
• Problems to work:
1)  Construct a multiplication table for multiplication mod 3

2) Construct an addition table and a multiplication table for addition and multiplication mod 5

3) The moduli we are most interested in are prime numbers. To see one reason for this, construct the multiplication table for multiplication mod 4. (It may not be obvious from the table that there is a problem: you might want to think about the zero product property from algebra. More next time.)

4) Translate the 8 entries in the addition and multiplication tables mod 2 into statements about the sums and products of even and odd numbers: three of them are translated in the notes above.

Thinking about the problem 7^(1942) mod 100

below the fold... This is a journal-like post, where I describe my thinking as I think through the problem

Finding remainders with the help of a calculator

Most calculators will not give you remainders directly. But we can use a form of the division algorithm together with the calculator to find a remainder when the long division would be too lengthy or tedious.

To recall, the division algorithms says that for any natural numbers m and n, there are whole numbers q and r (with r<n) such that
     m = n*q + r
Solving this for r, we can rewrite it as
    r = m - n*q
In this, m is the dividend, n is the divisor (or modulus), and q is the whole-number quotient when the dividend is divided by the modulus. We will use the calculator to find q and then to find r by the formula above.

The example I worked in class was finding 884736 mod 7.
Divide 884736 by 7 on the calculator. Here the dividend m is 884736 and the divisor n is 7. The calculated quotient will contain a decimal part: 126390.857142857...
So we just ignore everything after the decimal point to get q = 126390
Note: do not round: just ignore everything after the decimal point. (This is called "truncating".)

Now we can find the remainder r:
r = 884736 - 7*126390 = 884736 - 884730 = 6

No journal submissions tomorrow

As I said in class Tuesday, there will be no journal submission tomorrow (Thursday the 22nd). It would only include one day anyway, namely Tuesday. Just include that with next week's submission.

Make sure the previous 3 weeks are posted and, if necessary, that you have gone back and corrected the file names and the summary line of your post. Double-check these things even if I have not left an answer to your post yet.

And please make sure that the posts are private!

You do not need to make new posts, you can edit the posts that you already put up (even to change them to private questions).

[Cross-posted to Piazza]

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.

Test 1 logistics

Test 1 will take place in our usual classroom. However, the desks will have to be rearranged and there will be assigned seating. Therefore the test will take the whole period. 

Please make an effort to arrive on time. If you arrive while I am distributing the test papers, you will find the door locked and a sign asking you to wait until the test papers have been distributed. If this happens, please do not knock on the door, but wait quietly and I will open the door when I am finished.

(cross-posted to Piazza)

Tuesday 13 September class

Topics:
 • Theorem: the prime factorization of a natural number is unique (just stated, not proved) - this is also called the Fundamental Theorem of Arithmetic
• The division algorithm (we used to prove the missing step of the proof that there is no largest prime number): see below
 • Proving that there is no largest prime number, that is, that the number of prime numbers is infinite.

The division algorithm: (which is not really an algorithm at all)
If n and m are any natural numbers, then
       n = m•q + r
where q (for quotient) and r (for remainder) are natural numbers or 0, and r is less than m.

Comment: you already know this fact, you just may not have seen it written in algebraic language before. It is how we check a division problem when dividing with remainder.

Examples showing what the division algorithms says:  in all of these divisions, we have to forget about decimals and even fractions, and just divide natural numbers with remainders left over.

Example 1: Let n=23 and m=5. If we divide 23 by 5, 5 goes into 23 4 times and there is a remainder of 3. So the quotient here is q=4 and the remainder is r=3, and the division algorithm says
           23 = 5•4 + 3
Which is true.

Example 2: Let n=35 and m=5. If we divide 35 by 5, 5 goes into 35 7 times with remainder 0. So the division algorithm here says that
          35 = 5•7 + 0
Which is also true.

Example 3: Let n=3 and m=5. If we try to divide 3 by 5 (remember, without using decimals or fractions) we see that 5 does not "go into" 3, that is, 5 goes into 3 0 times, and the remainder is 3. So the division algorithm here says that
          3 = 5•0 + 3
Which is also true.

The last two examples show why we need to allow q and r to be 0 if necessary. Also, the remainder r is not allowed to be greater than m-1, in other words if we are dividing by 5 (as in the examples above) then the remainder must be 4 or less.

Special case:  (remainder 0) n is divisible by m if and only if n = mq for some natural number q.
(We will use this later when proving that the square root of 2 is irrational, for example.)

How the division algorithm is used in the proof that there is no largest prime number: an example
We form the number N = 2•3•5•7•11•13•17•19 + 1
We can then observe that N has remainder 1 when divided by 2, by comparing to the division algorithm:
N = 2•(3•5•7•11•13•17•19) + 1, so in the division algorithm the quotient q is the quantity in parentheses, and the remainder r is 1.
Similarly N has remainder 1 when divided by 3, because we can rearrange the factors:
N = 3•(2•5•7•11•13•17•19) + 1
And similarly N has remainder 1 when divided by 5, because we can rearrange the factors:
N = 5•(2•3•7•11•13•17•19) + 1
And so on with the other prime numbers 7 through 19. Each one gives remainder 1 when we divide by it.

• Modular arithmetic (introduction and terminology/notation)
Activity to start with: operations on even/odd numbers
• Modular arithmetic: some vocabulary and notation (from the Art of Problem Solving  reading, as well):
  modulus: the number we are "dividing out"
  residue: the remainder when dividing by the modulus
  notation: a ≡ b (mod m)
                 read it as: "a is congruent to b mod m"
                 it means: a-b is divisible by m, or equivalently, that a and b have the same remainder when divided by m
   In case b is a residue mod m, a ≡ b (mod m) means that b is the remainder when a is divided by m.

Getting used to this language/notation:

So in the example of "clock arithmetic", the modulus is 12, the possible residues are the integers 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, and 11; and we can say for example that 98 ≡ 2 (mod 12) because 2 is the remainder we get when we divide 98 by 12.

Homework:
• Journal assignment: Write out the proof that there is no largest prime number, including an explanation for how you know that N is larger than p, and how you know that N is not divisible by any of the primes 2 through p.
Problems:
1) State the division algorithm for each of the following cases:
    a) n=31, m=4 (that is, dividing 31 by 4)
    b) n=60, m=3 (that is, dividing 60 by 3)
    c) n=7, m=11 (that is, dividing 7 by 11)

Next topic: more on Modular arithmetic (reading from The Art of Problem Solving) and connecting it to the odd/even activity.