# HW3: Due Fri 9th Feb before 11:59:59pm

Q1. (10 points) Is $$4^{1536} \equiv 9^{4824} \mod 35$$? Show all work to support your answer. Hint: 35 is not a prime so you cannot apply Fermat's little theorem directly. However, 35 is a product of primes and you can apply the theorem to those prime factors. You can also use modular exponentiation approach (but show all steps).

Q2. (10 points) Solve $$x^{86} \equiv 6 \mod 29$$, i.e., find the value $$x$$ for which the equation is true. Hint: You can use fermat's little theorem.

Q3. (10 points) Prove that $$gcd(F_{n+1}, F_n) = 1$$, for $$n \ge 1$$, where $$F_n$$ is the n-th Fibonacci element.

Q4. (10 points) Assume that the cost to multiply a n-bit integer with a m-bit integer is O(nm). Given integers x and y with n-bits and m-bits, respectively, give an efficient algorithm to compute $$x^y$$. Show that the method is correct, and analyze its running time.

# Important:

You must show all the detailed steps to get credit for a question.

Submission must be in PDF format only.