中国余剰定理 - Summer498 の頭ん中

中国余剰定理

孫子算経に載っているらしい。

互いに素である$ n個の自然数$ m_1,\cdots,m_nを用意する

$ \forall i,j\in\N_{\le n}^+\quad(m_i,m_j)\in{\rm\mathcal Cop}

$ \Rightarrow以下の式を満たす全単射$ f:\prod_{i=1}^n(\Z/m_i\Z)\ \leftrightarrow\ (\Z/M\Z)が存在

$ M= \prod_{i=1}^n m_i

$ x\overset{M}\equiv f(a_1,\cdots,a_n)

$ \left\{\begin{matrix}x\overset{m_1}\equiv a_1\\\vdots\\x\overset{m_n}\equiv a_n\end{matrix}\right.

ガウスの整数論に一般的な証明が載っているらしい。

証明

$ M_i=\frac{M}{m_i}とする。

特に$ i\ne jのとき$ m_i|M_j

$ m_iと$ M_iは互いに素なので以下の一次不定方程式の整数解$ t_i, u_iが存在する

$ t_iM_i+u_im_i=1

これを合同式で表すと

$ t_iM_i\overset{m_i}\equiv1

$ x:\overset M\equiv\sum_{k=1}^na_kt_kM_kと定めると、

$ x\overset{m_i}\equiv a_it_iM_i$ \quad$ \because j\ne i\ \Rightarrow\ m_i|M_jであるため。

$ =a_i$ \quad$ \because t_iM_i\overset{m_i}\equiv1より

唯一性

任意の解$ yについて

$ y\overset{m_i}\equiv a_i

$ x-yを計算すると

$ x-y\overset{m_i}\equiv a_i-a_i=0

$ \therefore x\overset {m_i}\equiv y

系3

1. $ n=\prod_{p\in\mathbb P|n}\hat p\quad(\hat p=p^{w_p})と分解できるとき

$ \hat p同士は互いに素であるため

$ (\Z/n\Z)\simeq\prod_{p\in\mathbb P|n}(\Z/\hat p\Z)

更に$ \{0\}を取り除くことで乗法群も対応付けられる

2. $ (\Z/n\Z)^\times\simeq\prod_{p\in\mathbb P|n}(\Z/\hat p\Z)^\times