Math 480, Spring 2015, Assignment 7
From cartan.math.umb.edu
Carefully state the following theorems (you do not need to prove them):[edit]
- Chinese remainder theorem (asserting that certain maps are group isomorphisms).
- Time and memory bounds for computing the isomorphisms of the Chinese Remainder Theorem and their inverses.
Solve the following problems:[edit]
- Exercises 2.19 and 2.20.
Coding projects:[edit]
- (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.)
- (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$.
