中国余剰定理
$ \forall m,n\in\N^+
$ \gcd(m,n)=1
$ \Rightarrow\begin{cases}x={\rm f}_{m,n}(a,b)\overset m\equiv a\\x={\rm f}_{m,n}(a,b)\overset n\equiv b\end{cases} を満たす全単射$ {\rm f}_{m,n}:(\Z/m\Z)\times(\Z/n\Z)\leftrightarrow(\Z/m\,n\,\Z)が存在
全単射を論理式でまとめて書けたら全部を論理式で書けるんだが…Summer498.icon
証明
1. $ xが存在する
$ \gcd(m,n)=1 より$ ^{\exist s,t\in\Z}[m\,s+n\,t=1]
$ x={\rm f}_{m,n}(a,b)=b\,m\,s+a\,n\,tとすると
$ x\overset m\equiv a
$ x=(b\,s)m+a(n\,t)
$ =(b\,s)m+a(1-s\,m)
$ \overset m\equiv a
$ x\overset n\equiv b
$ x=(a\,t)n+b(m\,s)
$ (a\,t)n+b(1-t\,n)
$ \overset m\equiv a
2. $ xが唯一である
$ x_1, x_2が$ \begin{cases}x\overset m\equiv a\\x\overset n\equiv b\end{cases}を満たす$ xだと仮定
$ \begin{cases}x_1-x_2\overset m\equiv a-a=0\\x_1-x_2\overset n\equiv b-b=0\end{cases}が成立
$ \Leftrightarrow x_1-x_2\overset{m\,n}\equiv0
つまり$ x_1\overset{m\,n}\equiv x_2
$ x\in(\Z/m\,n\,\Z)は唯一
3. $ {\rm f}_{m,n}は全単射
$ ^{\forall x\in(\Z/m\,n\,\Z),\ \exist!a\in(\Z/m\Z)}[x\overset m\equiv a]
$ a_1,$ a_2が$ x\overset m\equiv aを満たす$ aだと仮定
$ a_1-a_2\overset m\equiv x-x=0が成立
つまり$ a_1\overset m\equiv a_2
$ a\in(\Z/m\Z)は唯一
$ ^{\forall x\in(\Z/m\,n\,\Z),\ \exist!b\in(\Z/n\Z)}[x\overset n\equiv b]
$ aと同様に唯一性を示せる
系
1. $ ^{\forall m,n\in\N^+}[\gcd(m,n)=1\Rightarrow(\Z/m\,n\,\Z)\simeq(\Z/m\Z)\times(\Z/n\Z)]
2. $ ^{\forall m,n\in\N^+}[\gcd(m,n)=1\Rightarrow(\Z/m\,n\,\Z)^\times\simeq(\Z/m\Z)^\times\times(\Z/n\Z)^\times]
$ \begin{cases}{\rm f}_{m,n}(a_1,b_1)=x_1\\{\rm f}_{m,n}(a_2,b_2)=x_2\end{cases}\Leftrightarrow{\rm f}_{m,n}(a_1a_2,b_1b_2)=x_1x_2
証明
$ \begin{cases}x_1={\rm f}_{m,n}(a_1,b_1)\overset m\equiv a_1\\x_1={\rm f}_{m,n}(a_1,b_1)\overset n\equiv b_1\\x_2={\rm f}_{m,n}(a_2,b_2)\overset m\equiv a_2\\x_2={\rm f}_{m,n}(a_2,b_2)\overset n\equiv b_2\end{cases} を満たす全単射$ {\rm f}_{m,n}が存在するので、
$ \begin{cases}x_1x_2={\rm f}_{m,n}(a_1a_2,b_1b_2)\overset m\equiv a_1a_2\\x_1x_2={\rm f}_{m,n}(a_1a_2,b_1b_2)\overset n\equiv b_1b_2\end{cases}