Problem 1- Find the following (make sure to justify your answers):

(a) The remainder when 3⁶⁵ is divided by 17.

(b) The smallest positive integer s such that 3^s ≡ 1 (mod 11).

(c) All integers n such that n ≡ 1 (mod 6) and n ≡ 4 (mod 11).

(d) The value of φ(40000).

(e) The number of integers between 1 and 260 (inclusive on both sides) relatively prime to 260.

(f) The last two digits of 13²⁴² when it is written out in base 10.

(g) The order of 4 modulo 25.

(h) All integers n such that n ≡ 24 (mod 35) and n ≡ 37 (mod 60).

(i) A unit modulo 18 that has order φ(18).

Problem 2- (Non-Collaboration Problem) Professor Yvonne has two classes: her MTH 561 class has 91 students and her MTH 332 class has 67 students. She brings two identical bags of leftover Valentine's Day candy to her classes. After distributing the candy evenly among the students in each class, there are 7 pieces of candy left over from her MTH 561 class and 3 pieces of candy left over from her MTH 332 class. Assuming she brought fewer than 5000 pieces of candy, how much candy did she bring, in total?

Problem 3- Consider the problem of finding the remainder when 2⁴⁰⁹⁶ is divided by 209 = 11 · 19. (Note that 4096 = 2¹².)

(a) Solve the problem using successive squaring only.

(b) Solve the problem by using Euler's theorem to reduce the size of the exponent.

(c) Solve the problem by computing 2⁴⁰⁹⁶ modulo 11 and modulo 19 separately, then using the Chinese Remainder Theorem to determine the result modulo 209.

(d) Suppose you are asked to compute 55106124962340^{21249128358912345234645734632545799924810134} modulo pq, where p = 32475982347098567309881 and q = 43498562345124558203957. (Those values p and q are both prime.) Without actually doing the calculation, which of the methods (a)-(c) would be most efficient? Explain.

(e) Suppose you are asked to compute 435982734598903^{3383813130965025124879127509} modulo N, where N = 7744741790817390591346888684194109280552294660156966848393176951664990066038619102280424270079583. Without actually doing the calculation, which of the methods (a)-(c) would be most efficient? Explain.

Problem 4- Answer the following:

(a) Suppose that N = pq and φ = (p - 1)(q  - 1), where p, q are real numbers with p < q. Find a formula for p and q in terms of N and φ.

(b) Given the information that N is a product of two primes, where

N = 8130390764015866244802763

φ (N) = 8130390764010072092213320

find the prime factors of N. (Do not use a computer except to do real number arithmetic.)