For every problem below, you must show detailed derivation steps.

1. Groups

[0.25 point] What is and ? What is and

[0.25 point] Abbreviating by . Define to be the set . Enumerate all the elements of ?

[1 point] For every , define “” as

Prove that is a group under the definition of “”.

[1 points] Find a definition of “” over such that is a group with respect to your definition of “”, and prove it.

2. Extended Euclidean and Greatest Common Divisors

[1.5 points] For every pair of and below, find integers and such that

(1) .

(2) .

[1 point] Write a Haskell function extended_euclideanon your own to automate your mechanical work above.

3. Chinese Remainder Theorem

[2 points] For each one of the below, If such an integer exists, find the minimal positive that satisfies each one of the following; otherwise, explain why such cannot be found.
(1)

(2)

[0.5 point] Write a Haskell function on your own that solves any equation systems of the following form for input integer arguments .

4. Euler's Theorem and Chinese Remainder Theorem

[0.5 point] Let be the Euler's totient function. Calculate .

[2 points] Without using a calculator, compute .

5. (Optional) Bonus problems (Step details are required to earn points.)

[2 points] Write a Haskell function to solve the following system of modulo equations for , where are input parameters.

[4 points] Write a Haskell function to solve the following system of modulo equations for , where for all positive integer , are positive integer inputs.