Problem 1. Using Modular Arithmetic.

(a) Divide 3⁷ by 7 and write in the form of a whole number plus a remainder

(b) Use this to determine the number a if 3⁷ ≡ a (mod 7).

(c) State how Fermat's little theorem could have allowed you to obtain this answer without calculation.

Problem 2. The Euclidean algorithm.

(a) Use the Euclidean algorithm to calculate the greatest common divisor of 94 and 12.

(b) Use the Euclidean algorithm to calculate a when 3a ≡ 1 (mod 20). (a is the multiplicative inverse of 3 (mod 20).)

Problem 3. Am I beautiful?

In class we saw that each successive term in the Fibonacci sequence is obtained by adding together the previous two numbers. We start with a₀=0, then a₁=1. Then to get a₂ we add a₀ and a₁. This gives 0+1=1 so a₂=1. The next number is a₃=1+1=2. The next number is a₄=1+2=3. And so on.

(a) Write down the next four numbers a₅, a₆, a₇ and a₈ in the Fibonacci sequence.

(b) Now calculate a₁/a₀, a₂/a₁, a₃/a₂, a₄/a₃, a₅/a₄, a₆/a₅, a₇/a₆ and a₈/a₇. Now calculate (1+√5)/2. What do you notice about these numbers? The value you get is called the Golden Ratio.

(c) Now we are going to make what is called a Golden Rectangle. The length of the shorter side is 1 metre. The length of the longer side is equal to the value you obtained for a₈/a₇ metres. Calculate the ratio of the sum of the larger and smaller side lengths to the larger side length. What do you notice about this value?

(d) It is said that if your face fits nicely into the Golden Rectangle then you are deemed beautiful. Find a photograph of yourself and calculate the length of your head and divide this by the width of your head. How close are you to the Golden Ratio? Based on this result, do you think this statement about beauty being related to the Golden Ratio is true?!

Problem 4. RSA Cryptography.

We want to receive a code secretly using RSA cryptography. First we choose two prime numbers, say p=5 and q=11. p and q are kept secret.

(a) Calculate n=pxq. n is made public.

(b) Now find m, the lowest common multiple of p-1 and q-1. We keep m secret.

Next we choose a number r that contains no commmon factors with m. We will choose r=3 here. r is also made public.

(c) Using the results of the question 2(b) find t, the multiplicative inverse of r (mod m). We keep t secret.

We now wish to receive a number from a sender without anyone finding out what this number is. Recall that n and r are both public.

(d) The sender wants to send the number a=5 to us. To do this they calculate the number b where a^r ≡ b (mod n). Calculate b by dividing a^r by n and finding the remainder. This is the number that the sender sends to us publicly. Note that an external observer has no way of calculating a using only b, n and r (the numbers that are available publicly).

(e) We receive the number b and want to decode to find a. To do this we calculate b^t (mod n) by dividing b^t by n. If you have done everything correctly you should get back a! This is how information is transmitted securely over the internet.

(f) Explain two strategies that are currently used to try and decrypt information that is coded using the RSA algorithm.