中国剩余定理证明

$$
dp = d \mod {p-1}
\dq = d \mod {q-1}
\e = 65537

\CRT
\left { \begin{array}{c}
x \equiv a_1 \mod n_1
\x \equiv a_2 \mod n_2
\...\end{array}
\right .

\n_1,n_2,...,n_i两两互素
\x一定存在，且存在构造法可解

\令M = \prod_{1}^{k}{n_i}
\有M_i = \frac{M}{n_i}
\设M_i' 使得，M_i'* M_i \equiv 1 mod n_i
\则x = \sum_{1}^{i}a_i * M_i * M_i'  \mod {M}

\ (a+b) \mod n = a \mod n + b \mod n

\ 证x\equiv a_k \mod n_k
\ 当i=k:
\(a_k * M_k * M_k' \mod M) \mod n_k
\= a_k * M_k * M_k' \mod n_k
\= a_k \mod n_k
\
\当i \ne k:
\(a_i * M_i * M_i' \mod M) \mod n_k
\a_i * \frac{M}{n_i} * M_i' \mod n_k
\=0

\
\d = dp \mod {p-1}
\d = dq \mod {q-1}

\令g = gcd(p-1,q-1)
\p-1 = g*k_p,q-1 = g *k_q

\\left { \begin{array} {c}
d \equiv d_1 \mod g
\ d \equiv d_2 \mod k_p
\ d \equiv d_3 \mod k_q
\end{array}
\right .

\ d \equiv dp \mod g
\dp = d \mod {p-1}
\dp = d \mod {k_qg}
\(d \mod {k_qg}) \equiv dp \mod p-1
\
\\left { \begin{array} {c}
d \equiv dp \mod g
\ d \equiv dp \mod k_p
\ d \equiv dq \mod k_q
\end{array}
\right .

$$