Clarification about the proof of the Chinese Remainder Theorem Near the end, the proof states that no prime that divides $m_i$ for $i = 1, 2,\ldots, k-1$ can divide $m_k$. But why does this imply that $\gcd{(m_1m_2\cdots m_{k-1},m_k)=1}$? I've been thinking about this for a long time, and I really can't understand it.


 A: If $\gcd(a,c)=1$ and $\gcd(b,c)=1$, then $\gcd(ab,c)=1$, because neither $a$ nor $b$ have any prime factors in common with $c$, and therefore nor does $ab$. This property holds because the $\gcd$ function is multiplicative.
A: A common divisor of $m_1, m_2, \dots, m_k$ Has to divide every one of $m_1, m_2, \dots, m_k$. So if a prime number divides  $m_1, m_2, \dots, m_{k-1}$ and also $m_k$, then it is also a common divisor of  $m_1, m_2, \dots, m_k$. This is a contradiction if the gcd is $1$.
A: To help you understand the Chinese Remainder Theorem: Let $P=\prod_{i=1}^k m_i$ where the $m_i$'s are non-$0$ and pair-wise co-prime.
(1). We establish that  if $x\equiv y \pmod {m_i}$ for every $i$ then $P|(x-y).$
(2). Let $[[P]]=\{1,...,P\}$ and let $S$ be the set of all $k$-tuples $(a_1,...,a_k)$ where $1\le a_i\le m_i$ for each $i.$
Let $F:P\to S$ where $F(x)=(\,f_1(x),...,f_k(x)\;)$ with  $x\equiv f_i(x)\pmod {m_i}$ for each $i$.
Now $F$ is a 1-to-1 function. Because $F(x)=F(y)$ implies $x\equiv f_i(x)=f_i(y)\equiv y \pmod {m_i}$ for every $i$, which by (1) implies $P|(x-y)\land |x-y|<P
$, implying $x=y$.
So the finite sets $[[P]],S$  have the same number of members, and $F:[[[P]]\to S$ is 1-to-1. So for each $(a_1,...,a_k)\in S$ there is exactly one $x\in [[P]]$ such that $F(x)=(a_1,...,a_k).$
