中国剰余定理

1. 概要 本記事では，中国剰余定理（Chinese Remainder Theorem, CRT）について解説します．中国剰余定理は，どの $2$ つも互いに素であるような正整数 $m_0,m_1,\ldots,m_{n-1}$ に対して，合同式 $$ x\equiv a _ 0\pmod{m _ 0},\quad x\equiv a _ 1\pmod{m…