Homework 5
Due on Nov 28 Monday

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

## 1. Groups

1. [0.25 point] What is and ? What is and

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

3. [1 point] For every , define “” as

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

4. [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. [1.5 points] For every pair of and below, find integers and such that

(1) .

(2) .

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

## 3. Chinese Remainder Theorem

1. [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)

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

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

2. [2 points] Without using a calculator, compute .

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

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

      crt3 :: (Int, Int) -> (Int, Int) -> (Int, Int) -> Int
crt3 = undefined
2. [4 points] Write a Haskell function to solve the following system of modulo equations for , where for all positive integer , are positive integer inputs.

       crt_n :: [(Int, Int)] -> Int
crt_n = undefined
3. [4 points] Calculate with pen and paper .