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 17$
$x\equiv 10\bmod 16$
$x\equiv 4\bmod 11$
$x\equiv 0\bmod 7$

Start by solving
$x\equiv 3\bmod 7$ and $x\equiv 0\bmod 7$
$3+17k=7l$
$17k-7l=-3$
$17\tilde{k} +7\tilde{l} = 1$

$\longrightarrow 17=2\cdot 7+3$
$7=2\cdot 3+1$
$1=(5\cdot 7)-(2\cdot 17)$
$l=(-(-3))(5) = 15$
$x=105$
$x\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.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License