Start the Lab 1 Problem Set Home

Problem set 1: Cryptography – Part 1

Problem 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.

Divide 15 by 7. What is the remainder?
Based on this result, determine the number a in the expression 15≡ a (mod 7).

Calculate 15x15x15x15x15. Using this result, what is the remainder when you divide 759375 by 7?

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.

(b) There are actually three different ways of making the number 42 and two ways of making 44. Find these alternative combinations.

(c) Since McDonald's likes to save money they will always opt for the combination that involves the fewest number of boxes. Given this additional constraint, what is the best combination to choose to make up 42 and 44 nuggets?

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.

  0 x 5 cent stamp 1 x 5 cent stamp 2 x 5 cent stamp 3 x 5 cent stamp 4 x 5 cent stamp
0 x 17 cent stamp
1 x 17 cent stamp
2 x 17 cent stamp
3 x 17 cent stamp
4 x 17 cent stamp

(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.