s프레쏘

중국인의 나머지 정리

Chinese remainder theorem (CRT) 양의 정수들 $n_1,n_2,\cdots ,n_k$가 $1\le i\ne j\le k$, $gcd(n_i,n_j)=1$(서로소)를 항상 만족할때, 아래의 연립합동식이 법 $M=n_1{n}_2\cdots n_k$에 대해 유일한 해를 가진다. $$x\equiv a_1(\mathrm{mod}{n}_1)$$ $$x\equiv a_2(\mathrm{mod}{n}_2)$$ $$⋮$$ $$x\equiv a_k(\mathrm{mod}{n}_k)$$ 증명 ( 존재성과 유일성) $M=n_1{n}_2\cdots n_k$ $M_i=M/n_i$라고 할 때, $n_j\ne n_i$인 모든 $n_j$에 대해 $M_i\equiv 0(\mathrm{mod}{n}_j)$ 이다. $gcd(n_i,n_j)=1$이므로 (1외에 공유하는 인수가 없으므로) $g..