Solutions to Quiz # 7 for Dr. Z.’s Number Theory Course for Nov. 7, 2013

1. (3 points) Using the formula, find ϕ(3003).

Sol. of 1: Recall that the formula for ϕ(n) is given in terms of the prime-power decomposition promised by the Fundamental Theorem of Arithemetics . You write n as

n = ∏_{i=1}^{k} p_{i}^{α_{i}} ,

and then

ϕ(n) = n ∏_{i=1}^{k}(1 − \frac{1}{p_{i}}) .

We have

3003 = 3 · 7 · 11 · 13 ,

so

ϕ(n) = 3003 · (1 − \frac{1}{3})(1 − \frac{1}{7})(1 − \frac{1}{11})(1 − \frac{1}{13})

= 3 · 7 · 11 · 13 · (\frac{2}{3})(\frac{6}{7})(\frac{10}{11})(\frac{12}{13})

= 2 · 6 · 10 · 12 = 1440 .

Ans. to 1: ϕ(3003) = 1440.

2. ( 3 points) State and prove Euler’s Classical Formula for the sum-over-divisors of n of ϕ.

Solution of 2: The formula is

∑_{d|n} ϕ(d) = n .

The proof goes as follows. Write all the fractions \frac{i}{n} i = 1, 2 …, n (n of them), and reduce them, and look at the resulting denominators. The number of those fractions that have denominator n is ϕ(n), since this means that the numerator has no common prime divisors with the denominator n, has must be relatively prime to n. Of course each of the denominators that show up must be divisible by n, and for every such denominator d, the number of fractions with that denominator is ϕ(d) (since the fractions are reduced, meaning there is nothing to cancel). Adding up all the possibilities, gives the identity.

3. (4 points) For the following prime p and q (let n = pq) public key e, and encrypted message c

(i) Check that e is an OK key, i.e. that it is coprime to ϕ(n).

(ii) Find the deciphering key, d, such that de ≡ 1 (mod ϕ(n))

(iii) Suppose Alice sent you the encrypted message c. Check that this is an OK message (coprime to n), and if it is find her original message?, m p = 3 , q = 5 , e = 5 , c = 7 Sol. of 3: n = 3 · 5 = 15, ϕ(n) = (3 − 1)(5 − 1) = 2 · 4 = 8.

(i) here e = 5, and since gcd(5, 8) = 1, the key is OK! (ii) We need to find d = [5^{−1}]_{8}. By inspection (trying out everything from 2 to 7 we get d = 5 (by coincidence it is the same). We can also use the Extended Euclidean Algorithm

8 = 1 · 5 + 3

so 3 = 8 − 1 · 5. Next

5 = 1 · 3 + 2 ,

so 2 = 5 − 1 · 3 = 5 − 1 · (8 − ·5) = 2 · 5 − 1 · 8. Next

3 = 1 · 2 + 1 ,

so

1 = 3 − 1 · 2 = (8 − 1 · 5) − 1 · (2 · 5 − 1 · 8) = 2 · 8 − 3 · 5 ,

so

1 = 2 · 8 − 3 · 5 .

Taking this modulo 8 we get

(−3) · 5 ≡ (mod 8)

But −3 ≡ 5 (mod 8) so

5 · 5 ≡ (mod 8)

and once again (the long way), we have d = 5. (iii) c = 7, gcd(7, 15) = 1 so it is an OK message. To decipher it, we do

m ≡ c^{e} (mod n) ≡ 7^{5} (mod 15) .

7^{1} = 7 , 7^{2} = 49 ≡ 4 (mod 15) , 7^{4} = 4^{2} ≡ 1 (mod 15)

so 7^{5} ≡ 7^{1+4} = 7 · 7^{4} ≡ 7 · 1 ≡ 7 (mod 15) . Ans. to 3(iii): The original message, m = 7. (By coincidence it is the same!)