Problem 1: Zero divisors

An element a Z_n -{0} is said to be a zero divisor modulo n if ab ≡ 0 (mod n) for some b Z_n -{0}.

1. Explain why there are no zero divisors in Z_p when p is prime.
2. Find a zero divisor in Z₃₃.
3. What is the value of the first element to repeat in the sequence

4. Do you think it is possible to find a non-zero number x Z₃₃ and a number k ≥ 0 such that x^k ≡ 0 (mod 33)? Why or why not? Would your answer change for some RSA modulus n other than 33?
5. Suppose n is not required to be an RSA modulus. Can you find numbers n,x,k such that x ⁄≡ 0 but x^k ≡ 0 (mod n)?

In all cases, justify your answers.

Problem 2: Greatest common divisor

The definition of greatest common divisor can be extended naturally to a sequence of numbers (a₁,a₂,…,a_k), not all of which are zero; namely, it is the largest integer d ≥ 1 such that d∣a_j for all j = 1,2,…,k. Describe an efficient algorithm for computing gcd(a₁,…,a_k), and explain why it computes the correct answer.

Problem 3: Euler’s totient function

Compute ϕ(2600). Show your work.

Problem 4: Euler theorem

Compute 3⁶⁹⁹⁸⁴⁵ mod 2600.

Problem 5: Extended Euclidean algorithm

Use the extended Euclidean algorithm to solve the Diaphantine equation

Show the resulting table of triples as in slide 18 of lecture 9 notes.
[Note: You may write a program to produce the table if you wish, but these numbers are small enough to make it quite feasible to carry out the computation by hand or with the aid of a pocket calculator.]

Problem 6: Diffie-Hellman

[Textbook, p.216, problem 7.6.10]

Problem 7: Primitive roots

1. Find a primitive root g of p = 761 and use the Lucas test to prove that you have one.
2. Find a non-trivial¹ number g Z*₇₆₁ that fails to be a primitive root of p, and use the Lucas test to prove your answer correct.