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 $\mathbb{Z}^+_3$ and $\mathbb{Z}^+_5$? What is $\mathbb{Z}^\times_3$ and $\mathbb{Z}^\times_5$

  2. [0.25 point] Abbreviating $\mathbb{Z}^+_n$ by $\mathbb{Z}_n$. Define $\mathbb{Z}_p\times\mathbb{Z}_q$ to be the set $\{(g,h) | g\in\mathbb{Z}_p, h\in\mathbb{Z}_q\}$. Enumerate all the elements of $\mathbb{Z}_3\times\mathbb{Z}_5$?

  3. [1 point] For every $(g_1, h_1), (g_2, h_2)\in\mathbb{Z}_3\times\mathbb{Z}_5$, define “$+$” as

    \[(g_1,h_1)+(g_2,h_2) = (g_1+g_2 \mathrm{\ mod\ } 3, h_1 + h_2 \mathrm{\ mod\ } 5). \]

    Prove that $\mathbb{Z}_3\times\mathbb{Z}_5$ is a group under the definition of “$+$”.

  4. [1 points] Find a definition of “$\times$” over $\mathbb{Z}_3\times\mathbb{Z}_5$ such that $\mathbb{Z}_3\times\mathbb{Z}_5$ is a group with respect to your definition of “$\times$”, and prove it.

2. Extended Euclidean and Greatest Common Divisors

  1. [1.5 points] For every pair of $a$ and $b$ below, find integers $x$ and $y$ such that
    \[ax+by=\mathrm{gcd}(a,b). \]


    (1) $a=12, b=35$.

    (2) $a=21, b=28$.

  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 $x$ exists, find the minimal positive $x$ that satisfies each one of the following; otherwise, explain why such $x$ cannot be found.
    (1)

    \[\left\{\begin{array}{l} 2x = 5 \mod 17\\ 3x + 1 = 9 \mod 13. \end{array}\right. \]


    (2)

    \[\left\{\begin{array}{l} x = 5 \mod 15\\ 3x + 1 = 9 \mod 25. \end{array}\right. \]

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

    \[\left\{\begin{array}{l} x = a \mod b\\ x = c \mod d. \end{array}\right. \]

4. Euler's Theorem and Chinese Remainder Theorem

  1. [0.5 point] Let $\phi$ be the Euler's totient function. Calculate $\phi(36)$.

  2. [2 points] Without using a calculator, compute $2016^{11} \mod 24$.

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 $x$, where $a,b,c,m,n,k$ are input parameters.

    \[\left\{\begin{array}{l} x = a \mod m\\ x = b \mod n\\ x = c \mod k. \end{array}\right. \]
          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 $x$, where for all positive integer $i$, $a_i, m_i$ are positive integer inputs.

    \[x = a_i \mod m_i \qquad \mbox{ for all } i \]
           crt_n :: [(Int, Int)] -> Int
       crt_n = undefined

  3. [4 points] Calculate with pen and paper $(24^{1000}\times25^{1001}) \mod 2016$.