SciCoNet
SciCoNet
helpdelete

中国剰余定理は、複数の同じ剰余を持つ余りの数列から、それらの値を同時に求めることができる定理です。

具体的には、以下のような連立合同方程式を考えます。

x≡a1(modm1)x≡a2(modm2)⋮x≡an(modmn)\begin{aligned} x &\equiv a_1 \pmod{m_1}\\ x &\equiv a_2 \pmod{m_2}\\ & \vdots \\ x &\equiv a_n \pmod{m_n} \end{aligned}

ここで、a1,a2,⋯ ,ana_1, a_2, \cdots, a_nは整数、m1,m2,⋯ ,mnm_1, m_2, \cdots, m_nは互いに素な整数とします。このとき、この連立合同方程式は解を持ち、その解は

x≡b(modM)x \equiv b \pmod{M}

の形で表されます。ただし、bbは整数であり、M=m1m2⋯mnM=m_1m_2\cdots m_nです。

この定理の証明は、数学的帰納法によって行われます。まず、n=2n=2のとき、解はx≡a1+m1k≡a2+m2l(modm1m2)x\equiv a_1+m_1k\equiv a_2+m_2l\pmod{m_1m_2}の形で表され、k,lk, lは整数です。この式を整理することで、kkについての一次方程式を得ることができます。この一次方程式が解を持つことは、m1m_1とm2m_2が互いに素であることから従います。

次に、n>2n>2のとき、m1,m2,⋯ ,mnm_1, m_2, \cdots, m_nのうちの任意の二つを選び、それらをm1′,m2′m_1', m_2'とすると、m1′m_1'とm2′m_2'は互いに素であるため、n=2n=2の場合の定理を用いて、以下のような式を得ることができます。

x≡a(modm1′m2′)x≡a3(modm3)⋮x≡an(modmn)\begin{aligned} x &\equiv a \pmod{m_1'm_2'}\\ x &\equiv a_3 \pmod{m_3}\\ & \vdots \\ x &\equiv a_n \pmod{m_n} \end{aligned}

この式を解くことで、x≡b(modM)x\equiv b \pmod{M}の形で解が得られます。ここで、M=m1m2⋯mnM=m_1m_2\cdots m_nです。

以上より、中国剰余定理が成立することがわかりました。この定理は、暗号理論や誤り訂正符号の理論など、様々な分野で応用されます。

リンク

The Chinese Remainder Theore[EN]