Assignment 2-

1. (a) Solve the congruence equation 19x ≡ 3 (mod 32).

(b) Compute 1905¹⁸⁹ mod 2741 using at most 12 multiplications and at most 12 modular arithmetic reductions.

2. Alice wants to send a secret message to Bob using RSA. Bob creates the public key (n, e) = (37 · 89, 17). If C = 1516, what is M?

3. (a) Find all possible values of e, with 2 ≤ e ≤ 30, for which (61 · 97, e) is a valid public key for RSA encryption.

(b) Bob shouldn't publish too much information! During the RSA algorithm, Bob accidentally publishes φ(n). Show that, using n and φ(n) alone, an adversary (such as Eve L.) can determine p and q.

4. Determine all integers n for which n⁸⁰¹⁷ + n⁹⁷⁵ + n⁸⁶ + 1 is divisible by 91.

5. In this problem, we present a method for certifying an integer is prime. Suppose n ≥ 2 is a positive integer, and a is an integer in the set {1, 2, . . . , n - 1} such that gcd(a, n) = 1. The order of a with respect to n, denoted ord_n(a), is the smallest positive integer d such that a^d ≡ 1 mod n. In this problem, we will investigate properties of the order function.

(a) Determine ord₇(2), ord₇(3), ord₇(4), ord₇(5), ord₇(6).

(b) Show that if b is a positive integer then a^b ≡ 1 mod n if and only if ordⁿ(a)|b. Conclude that ord_n(a)|φ(n).

(c) Suppose n is prime, and d|φ(n). How many integers in {1, 2, . . . , n-1} are there whose order is exactly d? You may use without proof that if m is a positive integer, then

∑_d|mφ(d) = m.

6. Use the Chinese Remainder Theorem to find quick answers to the following questions:

(a) How many positive integer multiples of 13 have their last ten digits being 9876543210, in that order?

(b) A positive integer n is square-free if there is no prime number p such that p²|n. Prove or disprove: There is a sequence of 1, 000, 000 consecutive positive integers, none of which is square free.