Thursday 13 October class

Note: No journals are due this week. Hold on till next week.
Also don't forget that this class will not meet on Tuesday the 18th of October!
After Test 2 our next meeting will be Thursday the 20th.

Topics:
• Activity related to the video on Fermat's Little Theorem linked in last time's post.
• Review of reasoning I used in computing 7¹⁴⁹² (mod 100) (to remind that we could not just reduce the exponent mod 100) - see more on this below
• Showing why the RSA algorithm works (from my notes) - we only got through the first part of the proof on p. 3 of these notes, so it will continue next time.

More comments on the problem of computing exponential expressions in modular arithmetic:
I asserted and also gave an example in class to show that you cannot reduce the exponent (at least, not to the modulus you are starting with). I do not know if I wrote up my example in the blog, so here is an example (which may or may not be the one I did in class):

Suppose we want to compute 3¹⁸ (mod 5).
This can be found with a calculator by computing 3¹⁸ = 387420489, and then reducing mod 5, so we get 3¹⁸ ≡ 4 (mod 5).
But if we try to shortcut by reducing the exponent mod 5, we get 18 ≡ 3 (mod 5), so we would think that our answer could be computed by taking 3³ = 27 ≡ 2 (mod 5), which is not the correct answer.

Referring back to this post (or to the reading from Art of Problem Solving), the cases where we can reduce before performing the computations (and then reduce again, if necessary) are these:
• In addition or subtraction, we can reduce the numbers before adding or subtracting
• In multiplication, we can reduce the numbers before multiplying - (please note that there is no division in modular arithmetic)
• Because we can reduce factors before we multiply them together, we can reduce the base of a natural number exponent (since the base represents the factor which is being repeatedly multiplied together) before taking the power.

When it is the exponent which is "too big", other tricks must be used, such as looking for patterns in the powers of the base (as in the example of 7¹⁴⁹²) or using Fermat's Little Theorem (which is a special case of looking for patterns in the powers.)



Homework:
• Journal assignment: watch the video on Fermat's Little Theorem (which was assigned previously!), write on what you learn from it, and then use that to try the Activity again.
• Problems related to Fermat's Little Theorem:
1) Compute each of the following:
     a) 1⁴ (mod 5), 2⁴ (mod 5), 3⁴ (mod 5), 4⁴ (mod 5)
     b) 1⁶ (mod 7), 2⁶ (mod 7), 3⁶ (mod 7), 4⁶ (mod 7), 5⁶ (mod 7), 6⁶ (mod 7)
     c) How does Fermat's Little Theorem relate to the answers in (a) and (b)?
2a) Using Fermat's Little Theorem (not by direct computation), find 8000³⁰ (mod 31). You must verify that the conditions are correct to use the theorem in this problem.
  b) Compute 8000⁴ (mod 5).  The answer is not 1. Why doesn't this contradict Fermat's LittleTheorem?

Up next: Completing the verification of the RSA algorithm (showing why it works). Reread the part of the proof on p. 3 of the notes and make sure that you are following the reasoning being used at each step (even if you don't see where it is going yet). Next time we will outline or "flowchart" the proof to get a better idea of how it fits together.