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$.
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)
    &amp;= f\left( \left[\sum_{i=1}^k a_i m_i \right]_0  \right) \\
    &amp;= \sum_{i=1}^k f\left( [a_i m_i]_0  \right) \\
    &amp;= \sum_{i=1}^k a_i f\left([m_i]_0  \right) \\
    &amp;= \sum_{i=1}^k a_i e_i \\
    &amp;= ([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.
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 &amp; \equiv &amp; n_1 &amp; (\mod m_1) \\ n &amp; \equiv &amp; n_2 &amp;  (\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 &amp; \equiv &amp; n_1 &amp; (\mod m_1) \\ n &amp; \equiv &amp; n_2 &amp;  (\mod m_2) \\ &amp; &amp; \vdots &amp; \\ n &amp; \equiv &amp; n_k &amp; (\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 &amp; \equiv &amp; n_1 &amp; (\mod m_1) \\ n &amp; \equiv &amp; n_2 &amp;  (\mod m_2) \\ &amp; &amp; \vdots &amp; \\ n &amp; \equiv &amp; n_k &amp; (\mod m_k) \\ n &amp; \equiv &amp; n_{k+1} &amp; (\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 &amp; \equiv n_{k+1} \ (\mod lcm(g_1,\dots,g_k))\\ &amp; \equiv n_{k+1}\ (\mod lcm(gcd(m_1,m_{k+1}),\dots ,gcd(m_k,m_{k+1}))) \\ &amp; \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 &amp; \equiv &amp; s &amp; (\mod lcm(m_1,m_2,\dots,m_k)) \\ n &amp; \equiv &amp; n_{k+1} &amp;  (\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 &amp; \equiv &amp; n_1 &amp; (\mod m_1) \\ n &amp; \equiv &amp; n_2 &amp;  (\mod m_2) \\ &amp; &amp; \vdots &amp; \\ n &amp; \equiv &amp; n_k &amp; (\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 &amp; \equiv &amp; 1 &amp; (\mod 2) \\ n &amp; \equiv &amp; 2 &amp;  (\mod 4) \end{array}\right.$$
has no solutions, while the system

$$\left\{\begin{array}{cccc}n &amp; \equiv &amp; 1 &amp; (\mod 2) \\ n &amp; \equiv &amp; \pm 1 &amp;  (\mod 4)\end{array}\right.$$
does.