Math 480, Spring 2015, Assignment 7

Carefully state the following theorems (you do not need to prove them):

1. Chinese remainder theorem (asserting that certain maps are group isomorphisms).
2. Time and memory bounds for computing the isomorphisms of the Chinese Remainder Theorem and their inverses.

Solve the following problems:

1. Exercises 2.19 and 2.20.

Coding projects:

1. (Chinese Remainder Theorem with two factors) Write a function that takes as input two modular integers $a, b$ with $a\in\mathbb{Z}_m$ and $b\in\mathbb{Z}_n$ and $\mathrm{gcd}(m,n)=1$ and returns a modular integer $x\in\mathbb{Z}_{mn}$ which reduces to $a\ (\mathrm{mod}\ m)$ and to $b\ (\mathrm{mod}\ n)$. (Exercise 2.20 will be very helpful if you have forgotten details.)
2. (Chinese Remainder Theorem with $k$ factors) Write a function that takes as input a $k$-tuple of modular integers $a_1,\dots,a_k$ with $a_i\in\mathbb{Z}_{m_i}$ and $m_1,\dots,m_k$ pairwise relatively prime, and returns a modular integer $x\in\mathbb{Z}_{m_1\dots m_k}$ which reduces to $a_i\ (\mathrm{mod}\ m_i)$ for each $i$.

--------------------End of assignment--------------------