Problem set 1: Cryptography – Part 1Problem 1. Modular Arithmetic. What time does a clock read 5495 hours after 5 o'clock? Problem 2. Try Modular Multiplication. Choose some numbers X and Y and compute (a) X (mod 7) and (b) Y (mod 7). Now compute XY (mod 7) and X+Y (mod 7) and show that these equal the product of (a) and (b) and the sum of (a) and (b) respectively (taking the mod of any resulting numbers that are larger than 7, as we did in class). Problem 3. Speedy calculations. Problem 4. Colour mixing
In class we saw how we can transmit a secret colour from one person to another without an external observer knowing what that colour was. Explain how this works in practice through the use of an example.
Problem 5. Chicken McNugget numbers.
In class we saw a video (click for link) about ordering takeaway Chicken McNuggets at McDonald's.
We found that, because the restaurant only stocked boxes of 6, 9 and 20, some combinations of nuggets could not be ordered. The largest number that cannot be ordered is 43.
(a) Show how the numbers 42 and 44 can be made up of combinations of 6, 9 and 20.
Problem 6. Postage stamps.
We wish to post some mail and have just two varieties of stamp: a 5 cent stamp and a 17 cent stamp. We want to work out the largest number that we cannot make with these two stamp varieties.
(a) First construct the table below and fill in the boxes the corresponding combinations.
(b) We can use this table to say what the smallest number ending with a given digit is. For instance, we can see that any numbers with the last digit of 1 that are equal to or larger than 51 can be formed (by considering the 3x17 cent line). This means that we cannot make the numbers 1 ,11, 21, 31, or 41. Use the table to do the same thing for numbers ending in: 2; 3; 4; 5; 6; 7; 8; 9; and 0. (c) Use the results of part (b) to determine the largest number that cannot be made by 5 and 17 cent stamps. |