Prelim Problem 34 J.O

34. (Preliminary for T, April 17; finalized Sat, April 21)
a. State and prove the Chinese Remainder Theorem for integer congruences.

Write the first congruence as an equation in Z, say $x = a + my$ for some
$y \in \mathbb{Z}$. Then the second congruence is the same as
$a + my ≡ b \bmod n$.
Subtracting a from both sides, we get
$my \equiv b − a \bmod n$
Since $(m, n) = 1$, we know $m \bmod n$ is invertible. Let $m'$ be an inverse for $m \bmod n$,
so $mm' \equiv 1 \bmod n$. Multiplying through by $m'$
, we have $y \equiv m'(b − a) \bmod n$, so
$y ≡ m'(b − a) + nz$ where z \in \mathbb{Z}$]]. Then$x = a + my = a + m(m'(b − a) + nz) = a + m'(b − a) + mnz.$So if x satisfies the original two congruences it must have this form. Let’s now check this expression, for every$z \in Z$, really satisfies the original two congruences:$a + mm'(b − a) + mnz \equiv a + 0 + 0 \equiv a \bmod m$and$a + mm'(b − a) + mnz \equiv a + 1(b − a) + 0 ≡ b \bmod n$b. Use the proof/algorithm of the CRT to solve the bandits problem given in class.$x\equiv 3\bmod 17x\equiv 10\bmod 16x\equiv 4\bmod 11x\equiv 0\bmod 7$Start by solving$x\equiv 3\bmod 7$and$x\equiv 0\bmod 73+17k=7l17k-7l=-317\tilde{k} +7\tilde{l} = 1\longrightarrow 17=2\cdot 7+37=2\cdot 3+11=(5\cdot 7)-(2\cdot 17)l=(-(-3))(5) = 15x=105x\equiv 105\bmod 119$Not sure from here. c. Prove the abstract version of the CRT for two ideals: If$I,J\$ are coprime ideals of a commutative ring R with identity then it must be isomorphic to the euclidean product of the two because it must be since they are coprime ideals and that means it is homomorphic and there is a bijective function from the euclidean product of the two quotient relations to R/IJ

Theorem: If I,J are coprime ideals of a commutative ring R with identity, then R/IJ≅R/I×R/J.

page revision: 1, last edited: 17 Apr 2018 02:03