For every problem below, you must show detailed derivation steps.
[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 point] Write a Haskell function
extended_euclidean on 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.
[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.
crt3 :: (Int, Int) -> (Int, Int) -> (Int, Int) -> Int
crt3 = undefined
[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
[4 points] Calculate with pen and paper .