Definitions of the Chinese Remainder Theorem The Chinese Remainder Theorem can be stated in a few ways:
(i) If $N = N_1N_2\cdots N_k$ and the $N_i$ are pairwise coprime we have a canonical isomorphism $$\mathbb{Z}/N\mathbb{Z} \cong \mathbb{Z}/N_1\mathbb{Z} \oplus \cdots \oplus \mathbb{Z}/N_k\mathbb{Z}$$
(ii) For any $a_i \bmod N_i, \quad  i = 1,\ldots, k$ there exists an $a$ such that $a \equiv a_i \bmod N_i$ for all $i$.
My question is how are these definitions equivalent and how is the isomorphism in the first definition true?
Also, the value of $a$ can be found via the Euclidean Algorithm. That is, put $M_i = N/N_i$. By assumption $M_i$ and $N_i$ are relatively prime. Then find $X_i$ with $X_iM_i \equiv 1 \bmod N_i$ and put $$a = \sum_{i=1}^k a_iX_iM_i$$
I am also confused how this uses the euclidean algorithm and finds the value of $a$.
 A: To get a decent proof, we need to be a bit more formal.
Suppose $N_0 = \prod_{i=1}^k N_i$ where the $N_i$ are pairwise coprime.
Notationally, we will define $a..b$ to be the set $\{a, a+1, a+2, \dots, b\}$
Define $[n]_i = \{x \in \mathbb Z : x \equiv n \pmod{N_i} \}$.
Then  $\mathbb{Z}_{N_i} = \{ [n]_i : n \in \mathbb Z\}$.
Theorem. Define $f:\mathbb{Z}_{N_0} \to \bigoplus_{i=1}^k \mathbb{Z}_{N_i}$ by $f([x]_0) = ([x]_1, [x]_2, \dots, [x]_k)$. Then $f$ is an isomorphism.
Proof.
The proof that $f$ is a well-defined homomorphism can be found in just about any good group theory text. We will skip that because I am too lazy to type the whole thing out.
For $i = 1..k$, define $e_k \in \prod_{i=1}^k N_i$ by
$e_1 = ([1]_1, [0]_2, \dots, [0]_k)$
$e_2 = ([0]_1, [1]_2, \dots, [0]_k)$
$\phantom{e_8}\;\;\vdots$
$e_k = ([0]_1, [0]_2, \dots, [1]_k)$
We will show that, for $i \in 1..k$, there exists an $m_i \in \mathbb Z$ such that $f([m_i]_0) = e_i$.
We start by defining $M_1 = \dfrac{N_0}{N_1}$
Note that, for $i \in 2..k$, $M_i \equiv 0 \pmod{N_i}$.
This means that $f([M_1]_0) = ([M_1]_1, [0]_2, \dots, [0]_k)$.
Also, since the $N_i$ are relatively prime, $\gcd(M_1,N_1) = 1$. So there exists an $X_1 \in \mathbb Z$ such that $X_1 M_1 \equiv 1 \pmod{N_1}$. Let $m_1 = X_1 M_1$. It follows that $f([m_1]_0) = ([1]_1, [0]_2, \dots, [0]_k)$.
Using the same reasoning but changing the things that need to be changed, it follows that for $i \in 1..k$, there exists an $m_i \in \mathbb Z$ such that $f([m_i]_0) = e_i$.
Now it's pretty easy to show that $f$ is onto. Let 
$([a_1]_1, [a_2]_2, \dots, [a_k]_k) \in \bigoplus_{i=1}^k \mathbb{Z}_{N_i}$.
Define $a = a_1 m_1 + a_2 m_2 + \cdots + a_k m_k$. Because $f$ is a homomorphism,
\begin{align}
    f([a]_0)
    &= f\left( \left[\sum_{i=1}^k a_i m_i \right]_0  \right) \\
    &= \sum_{i=1}^k f\left( [a_i m_i]_0  \right) \\
    &= \sum_{i=1}^k a_i f\left([m_i]_0  \right) \\
    &= \sum_{i=1}^k a_i e_i \\
    &= ([a_1]_1, [a_2]_2, \dots, [a_k]_k)
\end{align}
So $f$ is onto. Since $|\mathbb Z_{N_0}| = |\bigoplus_{i=1}^k \mathbb{Z}_{N_i}| = N_0$. It follows that $f$ must also be one-to-one.
A: Very simple if you observe $M_i\equiv 0\mod N_j$ for all $j\ne i$. So this value for $a$ satisfies
$$a\bmod N_j =\sum_{i+1}^k (a_i X_iM_i \bmod N_j)=a_jX_jM_j\bmod N_j=a_j\bmod N_j.$$
Finding the inverse $X_i$  of $M_i$ modulo $N_i$ is done through the Extended Euclidean algorithm, which yields the coefficients $X_i$ and $Y_i$ of a Bézout's relation between $M_i$ and $N_i$:
$$X_iM_i+Y_iN_i=1.$$My answer to this  question shows how it works in practice.
Why the isomorphism?
There's a natural map:
\begin{align*}
\varphi\colon \mathbf Z&\longrightarrow \mathbf Z/N_1\mathbf Z\times\dots\times\mathbf Z/N_k\mathbf Z\\x&\longmapsto(x\bmod N_1,\dots, x\bmod N_k)\end{align*}
and its kernel is $N_1\mathbf Z\cap\dots\cap N_k\mathbf Z=N\mathbf Z\;$ because the $N_i$s are pairwise coprime. So we have an injective map
$$\overline\varphi\colon \mathbf Z/N\mathbf Z\longrightarrow \mathbf Z/N_1\mathbf Z\times\dots\times \mathbf Z/N_k\mathbf Z.$$
Now, condition (ii) says  $\varphi$, hence $\overline \varphi$, is surjective, hence an isomorphism.
A: If, for a prime $p$, $p^{\alpha_i}|m_i$, with $\alpha_i$ being the largest exponent with that property, then $p^{\alpha}|\operatorname{lcm}(m_1,m_2,\dots,m_k)$, where $\alpha=\max\{\alpha_i\}$. Similarly, the greatest common divisor of several numbers is the product of the largest powers of the primes that divide all the given numbers.
Associativity allows one to proceed a step at a time with an inductive argument without putting all eggs into a basket at once. Jumping at the opportunity I'll prove the most basic case of $k=2$.

Theorem 1 : Two simultaneous congruences
  $$\left\{\begin{array}{cccc}n & \equiv & n_1 & (\mod m_1) \\ n & \equiv & n_2 &  (\mod m_2)\end{array}\right.$$
  are only solvable when $n_1\equiv n_2 \ (\mod gcd(m_1,m_2))$. The solution is unique modulo $lcm(m_1,m_2)$.
  (When $m_1$ and $m_2$ are coprime their gcd is $1$. By convention, $a\equiv b\ (\mod 1)$ holds for any integers $a$ and $b$.)

Proof:
By a generalization of Euclid's algorithm, there are integers $s$ and $t$ such that
$$tm_1+sm_2=gcd(m_1,m_2).$$
Since $n_2−n_1\equiv 0 \ (\mod gcd(m_1,m_2))$, for some $t'$ and $s'$,
$$t'm_1+s'm_2=n_2−n_1.$$
Then $n=t'm_1+n_1=−s'm_2+n_2$ satisfies both congruences in the theorem. This proves the existence of a solution.
To prove the uniqueness part, assume $n$ and $N$ satisfy the two congruences. Taking the differences we see that
$N−n\equiv 0 \ (\mod m1)$ and $N−n\equiv 0\ (\mod m_2)$,
which implies $N−n\equiv 0 \ (\mod lcm(m_1,m_2))$.
As was previously stated, a more general theorem can now be proved by induction.

Theorem 2 : The simultaneous congruences
  $$\left\{\begin{array}{cccc}n & \equiv & n_1 & (\mod m_1) \\ n & \equiv & n_2 &  (\mod m_2) \\ & & \vdots & \\ n & \equiv & n_k & (\mod m_k)\end{array}\right.$$
  are only solvable when $n_i=n_j \ (\mod gcd(m_i,m_j))$, for all $i$ and $j$, $i\neq j$. The solution is unique $\mod lcm(m_1,m_2,\dots,m_k)$.

Proof :
Theorem 1 serves the initial step verification. Assume the theorem holds for $k$ congruences and consider $k+1$ of them.
$$\left\{\begin{array}{cccc}n & \equiv & n_1 & (\mod m_1) \\ n & \equiv & n_2 &  (\mod m_2) \\ & & \vdots & \\ n & \equiv & n_k & (\mod m_k) \\ n & \equiv & n_{k+1} & (\mod m_{k+1})\end{array}\right.$$
Let $s$ be a solution of the first $k$ equations. Then the congruence $n\equiv s \ (\ mod lcm(m_1,m_2,\dots,m_k))$ has a solution. (Observe that every solution of the latter also satisfies the first $k$ congruences.) To be able to apply the already proven Theorem 1, we need to show that
$$s\equiv n_k+1 (mod gcd(lcm(m_1,\dots,m_k),m_{k+1})).$$
Let's write $g_u=gcd(m_,m_{k+1})$, $u=1,\dots,k$. Then we know that $n_u \equiv n_{k+1}\ (\mod g_u)$ for these values of u. But $n_u=s+t_um_u$, for some $t_u$, implying $n_{k+1}=s+t_um_u\ (\mod g_u)$ so that
$$s=n_{k+1} \ (\mod g_u), u=1,2,\dots ,k.$$
If so,
\begin{align} s & \equiv n_{k+1} \ (\mod lcm(g_1,\dots,g_k))\\ & \equiv n_{k+1}\ (\mod lcm(gcd(m_1,m_{k+1}),\dots ,gcd(m_k,m_{k+1}))) \\ & \equiv n_{k+1}\ (\mod gcd(lcm(m1,…,mk),mk+1)),\end{align}
because $lcm(gcd(m_1,m_{k+1}),
\dots,gcd(m_k,m_{k+1})) =gcd(lcm(m_1,\dots,m_k),m_{k+1})$.
Thus the system
$$\left\{\begin{array}{cccl}n & \equiv & s & (\mod lcm(m_1,m_2,\dots,m_k)) \\ n & \equiv & n_{k+1} &  (\mod m_{k+1})\end{array}\right.$$
has a solution which is unique modulo $lcm(lcm(m_1,m_2,\dots,m_k),m_{k+1})=lcm(m_1,m_2,\dots,m_k,m_{k+1})$.
It also satisfies the whole set of $k+1$ congruences.

Corollary : The simultaneous congruences
  $$\left\{\begin{array}{cccl}n & \equiv & n_1 & (\mod m_1) \\ n & \equiv & n_2 &  (\mod m_2) \\ & & \vdots & \\ n & \equiv & n_k & (\mod m_k)\end{array}\right.$$
  where all $m_i$'s are pairwise coprime has a unique solution modulo $m_1\cdot m2\cdots m_k$.

If some $m_i$'s are not mutually prime, a solution may not exist unless the corresponding congruences agree. For example, the system 
$$\left\{\begin{array}{cccc}n & \equiv & 1 & (\mod 2) \\ n & \equiv & 2 &  (\mod 4) \end{array}\right.$$
has no solutions, while the system
$$\left\{\begin{array}{cccc}n & \equiv & 1 & (\mod 2) \\ n & \equiv & \pm 1 &  (\mod 4)\end{array}\right.$$
does.
