MTH 225(M) Exercise-Set #8

Due by 5 p.m. on April 15 (Wednesday)

In our textbook, read Section 4.1, and read Chapter 5 from the beginning through Section 5.4.

Please do exercises in teams of two. Doing so garners a 5% bonus.

Show intermediate steps/explanations for obtaining answers.

1. Use the scheme specified at the bottom of our textbook's page 207 to translate the following sequence of letters to numbers (don't do any ~~Caesar ciphering~~ here): "HELLO".
2. Using that same scheme, translate the following sequence of numbers back to letters:
  22 14 17 11 03
1. Enter code (presented in lectures) for 'fast' modular_exponentiation(int a, int e, int m) into a (Java) program.
  (Test it with examples from lectures and our textbook, e.g.
  as shown in a lecture, modular_exponentation(0708,37,10807) should return 8687;
  as shown in a lecture, modular_exponentation(8687,573,10807) should return 708;
  as shown in our textbook's Example 11 on page 227, modular_exponentation(3,644,645) should return 36;
  as shown at the top of our textbook's page 243, modular_exponentation(1819,13,2537) should return 2081;
  as shown at the top of our textbook's page 243, modular_exponentation(1415,13,2537) should return 2182;
  as shown near the bottom of our textbook's page 243, modular_exponentation(0981,937,2537) should return 0704; and
  as shown near the bottom of our textbook's page 243, modular_exponentation(0461,937,2537) should return 1115.
  But you don't need to submit anything showing these tests; this is just a suggestion for you to confirm that the code works properly.)
  Then, do the following:
2. Use the scheme specified at the bottom of our textbook's page 207 (don't do any ~~Caesar ciphering~~ here): to translate to numbers the first eight letters of your name, written with your last name first. E.g. my name with my last name first is "MCGUIREHUGH", the first eight letters of that are "MCGUIREH", and translating those letters to numbers yields the following:
  12 02 06 20 08 17 04 07
3. Make 'blocks' out of pairs of those eight numbers, and then use modular_exponentiation() to encrypt each block as in our textbook's Example 11 on pages 242-43. E.g. for me, making 'blocks' out of pairs of those eight numbers yields the following:
  1202 0620 0817 0407
  And then modular_exponentiation(1202,13,2537) returns 1225, modular_exponentiation(0620,13,2537) returns 72, modular_exponentiation(0817,13,2537) returns 1204, and modular_exponentiation(0407,13,2537) returns 1051, so encrypting those numbers yields the following numbers:
  1225 72 1204 1051
4. Further, as in our textbook's Example 12 on page 243, use modular_exponentiation() to decrypt the following numbers:
  2343 0710 2017
  E.g. (reproducing our textbook's Example 12 on page 243), suppose the numbers to be decrypted were as follows:
  0981 0461
  Well, modular_exponentiation(0981,937,2537) returns 0704, and modular_exponentiation(0461,937,2537) returns 1115. Separating those 'blocked' numbers 0704 and 1115 to translate them into letters yields the following:
  07 04 11 15
  Then, translating those numbers back into English letters yields the following:
  H E L P
  Thus, decrypting 0981 0461 yields "HELP".
For this exercise, include a printout of your program.
1. Enter code (presented in lectures) for multiplicative_inverse_of_e_modulo_f(int e, int f) into a (Java) program.
  (Test it with examples from lectures and our textbook, e.g.
  as shown in a lecture, multiplicative_inverse_of_e_modulo_f(7,20) should return 3;
  as shown in a lecture, multiplicative_inverse_of_e_modulo_f(13,20) should return 17;
  as shown in a lecture, multiplicative_inverse_of_e_modulo_f(37,10600) should return 573; and
  as indicated in our textbook's Example 12 on page 243, multiplicative_inverse_of_e_modulo_f(13,2436) should return 937.
  But you don't need to submit anything showing these tests; this is just a suggestion for you to confirm that the code works properly.)
  Then, do the following:
2. Use your program to determine the value d that is the multiplicative inverse of 42 modulo 137. Then also give the values of d·42 and d·42 mod 137.
3. Use your program to determine the value d that is the multiplicative inverse of 128 modulo 2009. Then also give the values of d·128 and d·128 mod 2009.
4. Explain why it doesn't work to try to obtain a value d that would be a multiplicative inverse of 616 modulo 2009. What might happen with the code (provided in a lecture)? (Ask the instructor if you're not sure how to manage assert.)
5. Similarly to the last part of the preceding exercise (B.3) and our textbook's Example 12 on page 243, decrypt a message (which should be an abbreviated question to which you should respond) which the instructor will provide to you. But use here 'key' numbers which are different from the key numbers used above and in the textbook, as follows:
  - Obtain a value e by appending 9 at the end of the last three digits of the telephone number listed for you in GVSU's People Finder (yielding a four-digit number).
    If you're working in a team (of two), it will suffice if you do this work for only one of you.
  - Obtain d as the multiplicative inverse of e modulo 12136.
  - Then, do decryption similarly to the last part of the preceding exercise (B.3) and our textbook's Example 12 on page 243 — but use your value of d, and n:=12367 here.
    (By the way, 12367 is 83*149, and 12136 is 82*148.)
  For example, my GVSU telephone number is 331-2915, so appending 9 at the end of the last three digits of that yields 9159 for my value for e.
  Then, multiplicative_inverse_of_e_modulo_f(9159,12136) returns 1863, so my value for d is 1863.
  Then suppose the message (which should be an abbreviated question) that I need to decrypt is as follows:
  10266 7409 3113 9231 1510 11763 6123 ?
  Well, modular_exponentiation(10266,1863,12367) returns 1300, modular_exponentiation(7409,1863,12367) returns 1204, modular_exponentiation(3113,1863,12367) returns 1707, modular_exponentiation(9231,1863,12367) returns 2412, modular_exponentiation(1510,1863,12367) returns 418, modular_exponentiation(11763,1863,12367) returns 2208, and modular_exponentiation(6123,1863,12367) returns 1704. Separating those 'blocked' numbers 1300, 1204, 1707, 2412, 418, 2208, and 1704 to translate them into letters yields the following:
  13 00 12 04 17 07 24 12 04 18 22 08 17 04 ?
  Then, translating those numbers back into English letters yields the following:
  N A M E R H Y M E S W I R E
  Thus, decrypting "10266 7409 3113 9231 1510 11763 6123 ?" yields "NAME RHYMES WIRE?".
  Since my name is "McGuire", my response to that question is "Yes" (more or less, I guess ;-) .
  By the way, if you get a number 30 which you're supposed to translate into an English letter, just ignore it.
For this exercise, include a printout of your program.

[5 points] Look at our textbook's Exercise 4.1.21 and its solution in the back. Some of the text of the solution is like the following:

    .
    .
    .
    2^k+1
      =           [by/because of        ?       ?       ?       ]
    2·2^k
      >           [by/because of        ?       ?       ?       ]
    k² + k²
      >           [by/because of        ?       ?       ?       ]
    k² + 4k
      ≥           [by/because of        ?       ?       ?       ]
    k² + 2k + 1
      =           [by/because of        ?       ?       ?       ]
    (k + 1)²
    .
    .
    .

But our textbook doesn't provide justifications for the individual steps. For this exercise, provide such justifications: copy the material above, and fill in the blanks. You may need to write a relatively large amount of text for some of the blanks; or feel free to actually add more intermediate steps.

Write a proof of the following: (∀n∈ℕ)[1 ≤ 2ⁿ]. Use induction.
Clearly label the basis step, the inductive step, and the inductive hypothesis.
Suppose a and b are two expressions such that a ≤ b. Then use that premise to write a proof of the following formula, which is the basis for our ability to cancel or multiply both sides of an inequality with a value (n): (∀n∈ℕ)[n·a ≤ n·b]. Use induction. Clearly label the basis step, the inductive step, and the inductive hypothesis.
Note: In your proof here you should not do any canceling or multiplying both sides of any inequality with any value because it's actually your job here to show that such will work; if you were to do such in the proof, then you would be guilty of doing circular reasoning.
Write a proof of the following formula: (∀n∈ℕ)[n ≥ 10 → n³ < 2ⁿ]
Use induction, and clearly label the basis step, the inductive step, and the inductive hypothesis.
[2 points] Do our textbook's Exercise 5.1.46.
Show intermediate steps/explanations for obtaining answers.
Determine cardinalities of sets for Exercise-Set #5's Exercise K actually various ways as follows:
1. [3 points] Write the cardinality for each little region in a Venn diagram. For example, the cardinality of the center region is 10:
  
  (You need to complete that diagram with a number in each little region.)
2. [2 points] Use your diagram from Part 1 above to determine the cardinalities of each of the sets (labeled [i]-[v]) specified in Part 2 of Exercise K in Exercise-Set #5.
3. [5 points] Use rules for counting (the inclusion-exclusion rule, the difference rule, etc.) and set identities (such as (∀S₁,S₂,S₃)[S₁ ∩ (S₁ ∪ S₂) = (S₁ ∩ S₂) ∪ (S₁ ∩ S₃)]) as another way to determine the cardinalities of those same five sets.
  Show intermediate work/explanations for obtaining answers.
[2 points] Explain why it must be true that if there are 30 students in a class, then there must be at least two who have last names that begin with the same letter.
In your answer for this exercise, name and use (a) principle(s) presented in this course.
[2 points] Give the following values:
- P(8,3)
- P(5,3)
- P(3,3)
Show intermediate steps/explanations for obtaining answers.
[2 points] How many possibilities are there for the first, second, and third positions in a horse race with 12 horses?
Show intermediate steps/explanations for obtaining answers. Show/use a formula/expression/principle for counting.
[2 points] Look at our textbook's Exercise 5.3.13 and its solution in the back of the book.
Briefly explain the solution.
[1 point] In how many ways can a set of four distinct letters be selected from the English alphabet? Your answer here can be simply in the form "P(something,something)" or "C(something,something)".
(Incidentally, look at our textbook's Exercise 5.3.15 and its solution in the back of the book.)
[8 points] Some (small) children like to put olives on the tips of their thumbs and fingers before eating them, e.g. as follows:

Note that each child here puts olives on the thumb and fingers of only one of their hands because they use their other hand to manipulate the olives, i.e. to pick them up and place them on fingertips (etc.). Note also that each thumb or finger can have only one olive on its tip: if one tries otherwise, the olives break and don't stay on. A final note is that these olives are all identical.
Incidentally, for the following work, consider using the symbols "T", "I", "M", "R", and "P" to designate one's thumb and fingers (Thumb, Index, Middle, Ring, Pinky).
1. 1. In how many different ways can a child like these 'wear' zero olives? Show/use a formula/expression/principle for counting.
  2. In how many different ways can a child like these 'wear' one olive?
    Remember that each child here puts olives on the thumb and fingers of only one of their hands.
    Show/use a formula/expression/principle for counting.
  3. In how many different ways can a child like these wear two olives?
    Suggestion: try this yourself with two identical twist ties or two identical rubber bands or something (real olives?!? ;-) . Consider keeping track of all the different ways the two olives may be placed by using the symbols "T", "I", "M", "R", and "P" to designate one's thumb and fingers (Thumb, Index, Middle, Ring, Pinky). Remember to put the two 'olives' on two different digits of one of your hands; don't put both 'olives' on any one of your digits, and don't put one 'olive' on a digit of one of your hands and the other 'olive' on a digit of your other hand.
    Show/use a formula/expression/principle for counting.
  4. In how many different ways can one wear three olives? Show/use a formula/expression/principle for counting.
  5. In how many different ways can one wear four olives? Show/use a formula/expression/principle for counting.
  6. In how many different ways can one wear five olives? Show/use a formula/expression/principle for counting.
  7. In how many different ways can one wear six olives?
    (See also The Princess Bride, by William Goldman. ;-)
    Show/use a formula/expression/principle for counting.
2. Then, answer the preceding questions ("In how many different ways can one wear zero/one/two/three/... olives?") again for the case where there are actually two different types of olives: some black, and some green. (Assume that all the black olives are identical, and all the green olives are identical.)
Show intermediate steps/explanations for obtaining answers.