連立合同式の解き方と解の存在条件(法が互いに素でない場合も)

本記事の内容

本記事は、連立合同式(合同式の連立方程式)の解の存在条件とその解き方について解説する記事です。

本記事を読むに当たり、合同式について知っている必要があるため、以下の記事も合わせてご覧ください。

合同式の法は自然数だけ？マイナスは？

...

for-spring.com

2023.03.15

「合同式を解く」ことの軽い復習

端的に言えば、「合同式を解く」というのは

です。
これは、合同式に限らず方程式についてもそうです。
要するに「未知数を求めること」が「解く」ということです。

「一次合同式を解く」とは？

今の話を厳密に書くと以下になります。

「合同式を解く」とは？

結局の所、合同式は解が一つの整数に定まるわけではありません。

より一般に、
$$
f(x)\equiv0\ ({\rm mod}\ m)\tag{\(\ast\)}
$$
という合同式に対して、\(x_0\)をこの合同式の1つの解とします。
\(x_1\equiv x_0\ ({\rm mod}\ m)\)とすれば、
$$
f(x_1)\equiv f(x_0)\equiv 0\ ({\rm mod}\ m)
$$
となります。
なぜなら、次が成り立つからです。

定理1.の証明は【代数学の基礎シリーズ】初等整数論編 その10を御覧ください。

すなわち、\(m\)を法として\(x_0\)と同じ同値類(整数の合同\(\equiv\)は同値関係だから)に含まれる整数はすべて(\(\ast\))の解なのです。

したがって、合同式を解くというのは、

ということになるわけです。

「類を求めること」なので、実は虱潰しに解を求めることができます。
なぜなら、\(m\)を法とすれば、\(\mathbb{Z}\)はちょうど\(m\)個の類に分けられるからです。
つまり、\(\mathbb{Z}\)は\(m\)で割り切れるグループ、\(1\)余るグループ、\(2\)余るグループ、\(\cdots\)、\(m-1\)余るグループの\(m\)個の類に分けられます。
したがって、これらを1つずつ当てはめてみれば良いわけなのです。

要するに、手数さえ厭わなければ、合同式を解くことができるのです。

「連立合同式を解く」とは？

これも同じです。

先程述べたように、この「未知の整数\(x\)を求める」というのは「\(x\)が含まれる同値類を求める」という意味です。

例えば、どんなのが連立合同式か？(こういう問題を解きたい)

例えば、こんなのが連立合同式です。
$$
\begin{cases}
x\equiv 3\ ({\rm mod}\ 4)\\
x\equiv 20\ ({\rm mod}\ 25)\\
\end{cases}
$$

また、こんなのも連立合同式です。
$$
\begin{cases}
x\equiv 4\ ({\rm mod}\ 15)\\
x\equiv 10\ ({\rm mod}\ 21)\\
\end{cases}
$$

今回は、「これらの問題を解きたいけど、どういうときに解が存在するのか？」について解説します。

「解き方だけ知りたいんだ！」という方は実際に解いてみるまで飛んで下さい。

連立合同式の解の存在条件①(法がどの2つも互いに素である場合)

では、本題です。

解の存在条件とその証明

要するに、

ということです。
もっと平たく言えば、法がどの2つも互いに素の場合は解ける、ということです(実はこの限りではありません)。

定理0.の証明

まず、(1)の第一の合同式、すなわち\(x\equiv a_1\ ({\rm mod}\ m_1)\)を満たすような\(x\in\mathbb{Z}\)は
$$
(\exists t\in\mathbb{Z})\ {\rm s.t.}\ x=a_1+m_1t\tag{2}
$$
を満たします。

この\(x\)が同時に第二の合同式、すなわち\(x\equiv a_2\ ({\rm mod}\ m_2)\)を満たしているため
$$
a_1+m_1t\equiv a_2\ ({\rm mod}\ m_2)
$$
です。

\(-a_1\equiv -a_1\ ({\rm mod}\ m_2)\)だから(実際、\(-a_1-(-a_1)=-a_1+a_1=0=0\times m_2\))、定理1.により
\begin{eqnarray}
a_1+m_1t\equiv a_2\ ({\rm mod}\ m_2)&\Longleftrightarrow&a_1+m_1t-a_1\equiv a_2-a_1\ ({\rm mod}\ m_2)\\
&\Longleftrightarrow&m_1t\equiv a_2-a_1\ ({\rm mod}\ m_2)\tag{3}
\end{eqnarray}
となります。

もっと単純に、\(a_1+m_1t\equiv a_2\ ({\rm mod}\ m_2)\)であるので
$$
(\exists t^\prime\in\mathbb{Z})\ {\rm s.t.}\ a_1+m_1t- a_2=m_2t^\prime
$$
であるから
$$
m_1t-\left( a_2-a_1\right)=m_2t^\prime
$$
となり、\(m_1t\equiv a_2-a_1\ ({\rm mod}\ m_2)\)を得る、としてもOKです。

ここで、次の事実を使います。

定理2.の証明は【代数学の基礎シリーズ】初等整数論編 その11を御覧ください。

さて、仮定から\(\gcd(m_1,m_2)=1\)であるため、\(t\)を未知数と見たときの合同式(3)は、類の意味で唯一の解を持ちます。
そしてその解は
$$
t=t_0+m_2s
$$
という形をしていて、\(m_2\)を法とする一つの剰余類(合同類)です。
これを(2)に代入すると、
\begin{eqnarray}
x&=&a_1+m_1t\\
&=&a_1+m_1\left( t_0+m_2s\right)\\
&=&a_1+m_1t_0+m_1m_2s
\end{eqnarray}
となります。
故に、\(x-\left(a_1+m_1t_0\right)=m_1m_2s\)だから、
$$
x\equiv\left(a_1+m_1t_0\right)\ ({\rm mod}\ m_1m_2)
$$
となります。

さて、今の今まで行っていたことは、
$$
\begin{cases}
x\equiv a_1\ ({\rm mod}\ m_1)\\
x\equiv a_2\ ({\rm mod}\ m_2)
\end{cases}
$$
の解を求めることです。

そもそも連立方程式を解くことは

です。
より論理的に書けば、今回の場合は

という問題です。
今まで行ってきたことは

であったわけで、そしてその解は\(x\equiv\left(a_1+m_1t_0\right)\ ({\rm mod}\ m_1m_2)\)だとわかりました。

したがって、もともとの連立方程式(1)
$$
\begin{cases}
x\equiv a_1\ ({\rm mod}\ m_1)\\
x\equiv a_2\ ({\rm mod}\ m_2)\\ \tag{1}
\qquad \quad\vdots\\
x\equiv a_k\ ({\rm mod}\ m_k)\\
\end{cases}
$$
を解くことは、
$$
\begin{cases}
x\equiv\left(a_1+m_1t_0\right)\ ({\rm mod}\ m_1m_2)\\
x\equiv a_3\ ({\rm mod}\ m_3)\\　\tag{1′}
\qquad \quad\vdots\\
x\equiv a_k\ ({\rm mod}\ m_k)\\
\end{cases}
$$
を解くことと同じ意味となるわけです。

故に、(1′)を新しい連立合同式と見て、
$$
\begin{cases}
x\equiv\left(a_1+m_1t_0\right)\ ({\rm mod}\ m_1m_2)\\
x\equiv a_3\ ({\rm mod}\ m_3)
\end{cases}
$$
を、先程と同様に解くことができます。

この操作を繰り返していけば、(1)の解が
$$
x\equiv x_0\ ({\rm mod}\ m_1m_2\cdots m_k)
$$
すなわち、\(x\equiv x_0\ ({\rm mod}\ M)\)として求まります。

定理0.の証明終わり

解の存在条件(別証明)

別証明もあります。

定理0.の別証明

$$
M=\prod_{n=1}^km_n=m_1m_2\cdots m_k
$$
とし、さらに
$$
M_n=\frac{M}{m_n}\quad (n=1,2,\cdots,k)\tag{4}
$$
で定めます。
つまり、\(M_n\)は\(m_1,\cdots,m_k\)の中で、\(m_n\)以外をかけ合わせた整数ということになります。

さて、このとき、
$$
M_nt_n\equiv 1\ ({\rm mod}\ m_n)\quad (n=1,2,\cdots,k)\tag{5}
$$
を満たす\(t_n\)を求めます。

このとき、連立合同式(1)の解は
$$
x\equiv a_1M_1t_1+a_2M_2t_2+\cdots+a_kM_kt_k\ ({\rm mod}\ M)\tag{6}
$$
となります。

何故かということを説明します。
もし\(x\)が(6)を満たしているとします。
\(M_1t_1\equiv1\ ({\rm mod}\ m_1)\)により\(a_1M_1t_1\equiv a_1\ ({\rm mod}\ m_1)\)が成り立ちます。
実際、\(a_1\equiv a_1\ ({\rm mod}\ m_1)\)であるため、再度定理1.から\(a_1M_1t_1\equiv a_1\ ({\rm mod}\ m_1)\)が成り立ちます。
したがって、
$$
(\exists l_1\in\mathbb{Z})\ {\rm s.t.}\ a_1M_1t_1=a_1+m_1l_1
$$
となります。
今、\(x\)は(6)を満たしているのですから、
$$
(\exists l_2\in\mathbb{Z})\ {\rm s.t.}\ x-\left(a_1M_1t_1+a_2M_2t_2+\cdots+a_kM_kt_k \right)=m_1\cdots m_kl_2
$$
を満たします。
これを変形して
\begin{eqnarray}
&&x-\left(a_1M_1t_1+a_2M_2t_2+\cdots+a_kM_kt_k \right)=m_1\cdots m_kl_2\\
&\Longleftrightarrow&x-\left\{(a_1+m_1l_1)+a_2M_2t_2+\cdots+a_kM_kt_k \right\}=m_1\cdots m_kl_2\\
&\Longleftrightarrow&x-a_1=m_1\left\{l_1+a_2\frac{M_2}{m_1}t_2+\cdots+a_k\frac{M_k}{m_1}t_k +m_2\cdots m_kl_2\right\}
\end{eqnarray}
となります。
ここで、(4)から
$$
M=m_1M_1=\cdots=m_kM_k
$$
ですので\(m_1| M_n\ (n=2,3,\cdots,k)\)です。
故に\(\displaystyle\frac{M_n}{m_1}\in\mathbb{Z}\ (n=2,3,\cdots,k)\)となります。
つまり、
$$
l_1+a_2\frac{M_2}{m_1}t_2+\cdots+a_k\frac{M_k}{m_1}t_k +m_2\cdots m_kl_2\in\mathbb{Z}
$$
となります。
したがって、\(x-a_1\)は\(m_1\)の倍数、すなわち
$$
x\equiv a_1\ ({\rm mod}\ m_1)
$$
を満たします。

この議論は\(m_1\)のみに対することではなく、全く同様にして\(x\equiv a_n\ ({\rm mod}\ m_n)\ (n=2,3,\cdots,k)\)を得ることができます。
したがって、
$$
(\forall n\in\left\{ 1,2,\cdots,k\right\})\ x\equiv a_n\ ({\rm mod}\ m_n)
$$
を得るから、(6)を満たす\(x\)は連立方程式(1)の解であるというわけです。

また、(1)の解は\(\ ({\rm mod}\ M)\)に関して唯一です。
実際、\(x\)および\(x^\prime\)を(1)の解とすれば、
\begin{eqnarray}
(\forall n\in\left\{ 1,2,\cdots,k\right\})\ x\equiv a_i\ ({\rm mod}\ m_i)
\end{eqnarray}
であり、かつ
\begin{eqnarray}
(\forall n\in\left\{ 1,2,\cdots,k\right\})\ x^\prime\equiv a_i\ ({\rm mod}\ m_i)
\end{eqnarray}
です。
整数の合同\(\equiv\)は同値関係だったということを思い出せば、反射律と推移律から
$$
\begin{eqnarray}
(\forall n\in\left\{ 1,2,\cdots,k\right\})\ x\equiv x^\prime\ ({\rm mod}\ m_i)
\end{eqnarray}
$$
となります。
すなわち、\(x-x^\prime\)は\(m_1,\cdots,m_k\)の全てで割り切れます。
今、\(m_1,\cdots,m_k\)はどの2つも互いに素であるため、\(m_1,\cdots,m_k\)の最小公倍数は\(M\)です。
故に、\(x-x^\prime\)は\(M\)で割り切れます。
これはまさに\(x\equiv x^\prime\ ({\rm mod}\ M)\)を表しています。

定理0.の証明終わり

解の存在条件②(法が互いに素でない場合)

例えば、次の連立合同式を①(法がどの2つも互いに素な場合)と同じように解いてみます。

$$
\begin{cases}
x\equiv 4\ ({\rm mod}\ 7)\\
x\equiv 7\ ({\rm mod}\ 10)
\end{cases}
$$

第一式により、解\(x\)は\(k\in\mathbb{Z}\)を用いて\(x=6k+4\)という形をしています。
故に、第二式により、\(k^\prime\in\mathbb{Z}\)を用いて
$$
6k+4-7=10k^\prime\Longleftrightarrow6k-3=10k^\prime
$$
を満たします。
\(6k-3=2\left(3k-2 \right)+1\)により\(6k-3\)は奇数です。
しかしながら、\(10k^\prime=2\times5k^\prime\)は偶数であり、偶奇性が一致しないため、この連立合同方程式は解が存在しません。

「じゃあ、この場合は解は存在しないの？」と思うかもしれませんが、そうではありません。
存在する場合もあります。

解の存在条件の明示と証明　(2つの合同式の場合)

定理3.の証明

(①\(\Longrightarrow\)の証明

連立合同式
$$
\begin{cases}
x\equiv a\ ({\rm mod}\ m)\\
x\equiv b\ ({\rm mod}\ n)\
\end{cases}
$$
が解\(x\)を持つとします。
このとき、\(a\equiv b\ ({\rm mod}\ d)\)を証明します。

第一式から解\(x\)は\(k_1\in\mathbb{Z}\)を用いて
$$
x=a+mk_1
$$
という形をしています。
また、\(x=a+mk_1\)が第二式も満たすので、\(k_2\in\mathbb{Z}\)を用いて
$$
a+mk_1-b=nk_2\Longleftrightarrow a-b=nk_2-mk_1
$$
となります。

\(m\)と\(n\)の最大公約数\(\gcd(m,n)\)は\(m\)の約数でもあり、同時に\(n\)の約数でもあります。
したがって、
$$
(\exists s,t\in\mathbb{Z})\ {\rm s.t.}\ m=\gcd(m,n)s,\quad n=\gcd(m,n)t
$$
となります。
故に、
$$
a-b=nk_2-mk_1=\gcd(m,n)tk_2-\gcd(m,n)sk_1=\gcd(m,n)\left( tk_2-sk_1\right)
$$
となるため、\(a\equiv b\ ({\rm mod}\ d)\)です。

(②\(\Longleftarrow\)の証明

逆に、\(a\equiv b\ ({\rm mod}\ d)\)だったとしましょう。
このとき、
$$
(\exists k_3\in\mathbb{Z})\ {\rm s.t.}\ a=b+dk_3=b+\gcd(m,n)k_3
$$
です。

次の定理を使います。

定理4.の証明は【代数学の基礎シリーズ】初等整数論編 その6を御覧ください。

定理4.から、\(mp+nq=d\)という\(p,q\in\mathbb{Z}\)が存在します。
今、\(a-b=dk_3\)であるから、
$$
mp+nq=\frac{a-b}{k_3}
$$
すなわち
$$
k_3mp+k_3nq=a-b
$$
です。
ここで、
$$
x=a+k_3mp=b-k_3nq
$$
とすれば、
$$
x-a=m\times k_3p,\quad x-b=n\times\left( -k_3q\right)
$$
となるので、
$$
x\equiv a\ ({\rm mod}\ m),\quad x\equiv b\ ({\rm mod}\ n)
$$
となるから、この\(x\)は連立合同式の解となります。

③解が存在するならば、\(l={\rm lcm}(m,n)\)を法として唯一であることの証明

仮に、解が\(x_1\)および\(x_2\)の2つ存在したとしましょう。
このとき、\(x_1\)および\(x_2\)は連立合同式
$$
\begin{cases}
x\equiv a\ ({\rm mod}\ m)\\
x\equiv b\ ({\rm mod}\ n)
\end{cases}
$$
の解ですので、
$$
x_1\equiv a\ ({\rm mod}\ m),\quad x_2\equiv a\ ({\rm mod}\ m)
$$
を満たします。
故に
$$
x_1\equiv x_2\ ({\rm mod}\ m)
$$
だから、
$$
(\exists k_1\in\mathbb{Z})\ {\rm s.t.}\ x_1-x_2=k_1m
$$
です。

一方で、
$$
x_1\equiv a\ ({\rm mod}\ n),\quad x_2\equiv a\ ({\rm mod}\ n)
$$
も満たします。
故に先程と同様にして
$$
(\exists k_2\in\mathbb{Z})\ {\rm s.t.}\ x_1-x_2=k_2n
$$
です。

以上のことから、\(x_1-x_2\)は\(m\)と\(n\)の公倍数です。

ここで、次の事実を使います。

定理5.の証明は【代数学の基礎シリーズ】初等整数論編 その3を御覧ください。

定理5.から、\(x_1-x_2\)は\(l={\rm lcm}(m,n)\)の倍数です。
したがって、
$$
(\exists K\in\mathbb{Z})\ {\rm s.t.}\ x_1-x_2=K\cdot {\rm lcm}(m,n)
$$
です。
これはまさに\(x_1\equiv x_2\ ({\rm mod}\ {\rm lcm}(m,n))\)を表しています。

定理3.の証明終わり

解の存在条件の明示と証明　(一般の場合)　※証明は抹茶様より提供

定理6.の証明　※抹茶様より提供頂いた証明に追記

①\(\Longrightarrow\)の証明

仮に解\(x\)が存在したとすると、\(1\leq i\leq n\)なる任意の\(i\in\mathbb{N}\)に対して
$$
x\equiv a_i\ ({\rm mod}\ m_i)
$$
が成り立つため、
$$
\begin{cases}
x\equiv a_1\ ({\rm mod}\ m_1)\quad (1)\\
x\equiv a_2\ ({\rm mod}\ m_2)\quad (2)\\
\end{cases}
$$
を満たしています。

このとき、(1)から、
$$
(\exists u_1\in\mathbb{Z})\ {\rm s.t.}\ x-a_1\equiv u_1m_1\Longleftrightarrow x=a_1+u_1m_1
$$
を満たします。

また、この\(x\)が同時に(2)も満たすので
$$
(\exists u_2\in\mathbb{Z})\ {\rm s.t.}\ x-a_2\equiv u_2m_2\Longleftrightarrow x=a_2+u_2m_2
$$
も満たします。

したがって、
$$
x=a_1+u_1m_1=a_2+u_2m_2
$$
を満たします。

そもそも、\(1\leq i\leq n\)なる任意の\(i\in\mathbb{N}\)に対して
$$
x\equiv a_i\ ({\rm mod}\ m_i)
$$
が成り立つため、今の操作を続けることで
$$
x=a_1+u_1m_1=a_2+u_2m_2=\cdots=a_n+u_nm_n
$$
を満たす\(u_3,\cdots,u_n\in\mathbb{Z}\)が存在します。

故に、\(1\leq i,j\leq n\)なる任意の\(i,j\in\mathbb{N}\)に対して
$$
x=a_i+u_im_i=a_j+u_jm_j
$$
です。
したがって、
$$
a_i-a_j=u_jm_j-u_im_i
$$
です。

ここで、\(\gcd(m_i,mj)\)は\(m_i\)の約数でもあり、また同時に\(m_j\)の約数でもあります。
故に、
$$
(\exists s,t\in\mathbb{Z})\ {\rm s.t.}\ m_i=\gcd(m_i,m_j)s,\ m_j=\gcd(m_i,m_j)t
$$
です。
したがって、
\begin{eqnarray}
a_i-a_j&=&u_jm_j-u_im_i\\
&=&u_j\cdot\gcd(m_i,m_j)t-u_i\cdot\gcd(m_i,m_j)s\\
&=&\gcd(m_i,m_j)\left( u_jt-u_is\right)
\end{eqnarray}
となるから、\(a_i\equiv a_j\ ({\rm mod}\ \gcd(m_i,m_j))\)です。

②\(\Longrightarrow\)の証明

逆に、\(a_i\equiv a_j\ ({\rm mod}\ \gcd(m_i,m_j))\)だったとしましょう。
すなわち、\(\gcd(m_i,m_j)\mid(a_i-a_j)\)とします。

このとき、再度定理4.を使います。

定理4.の証明は【代数学の基礎シリーズ】初等整数論編 その6を御覧ください。

定理4.から
$$
(\exists v_1,v_2\in\mathbb{Z})\ {\rm s.t.}\ m_iv_i+m_jv_j=a_i-a_j
$$
です。
つまり、
$$
a_i-m_iv_i=a_j+m_jv_j
$$
です。

このとき、\(x=a_i-m_iv_i=a_j+m_jv_j\)とすれば、
$$
x-a_i=m_i\cdot(-v_i),\quad x-a_j=m_j\cdot v_j\tag{3}
$$
です。

ここで、\(i,j\)は\(1\leq i,j\leq n\)を満たす任意の自然数だったわけですので、(3)は\(1\)から\(n\)までのすべてのペアに対して成り立っているということを指しています。

したがって、任意の\(1\leq k\leq n\)を満たす\(k\in\mathbb{N}\)に対して\(x\equiv a_k\ ({\rm mod}\ m_k)\)が成り立っているということになり、解の存在が証明完了です。

③解が存在するならば最小公倍数を法として唯一存在することの証明

仮に、解が\(x_1\)および\(x_2\)の2つ存在したとしましょう。
このとき、\(x_1\)および\(x_2\)は連立合同式

$$
\begin{cases}
x\equiv a_1\ ({\rm mod}\ m_1)\\
x\equiv a_2\ ({\rm mod}\ m_2)\\
\quad \quad \vdots\\
x\equiv a_2\ ({\rm mod}\ m_n)\\
\end{cases}
$$
の解ですので、
$$
x_1\equiv a_1\ ({\rm mod}\ m_1),\quad x_2\equiv a_1\ ({\rm mod}\ m_1)
$$
を満たします。
故に
$$
x_1\equiv x_2\ ({\rm mod}\ m_1)
$$
だから、
$$
(\exists k_1\in\mathbb{Z})\ {\rm s.t.}\ x_1-x_2=k_1m_1
$$
です。

一方で、
$$
x_1\equiv a_2\ ({\rm mod}\ m_2),\quad x_2\equiv a_2\ ({\rm mod}\ m_2)
$$
も満たします。
故に先程と同様にして
$$
(\exists k_2\in\mathbb{Z})\ {\rm s.t.}\ x_1-x_2=k_2m_2
$$
です。

以上のことから、\(x_1-x_2\)は\(m_1\)と\(m_2\)の公倍数です。

この操作を続けることによって
$$
x_1-x_2=k_1m_1=k_2m_2=\cdots=k_nm_n
$$
なる\(k_1,\cdots,k_n\in\mathbb{Z}\)が存在します。

ここで、再度定理5.を使います。

定理5.の証明は【代数学の基礎シリーズ】初等整数論編 その3を御覧ください。

定理5.から、\(x_1-x_2\)は\(l={\rm lcm}(m_1,m_2,\cdots,m_n)\)の倍数です。
したがって、
$$
(\exists K\in\mathbb{Z})\ {\rm s.t.}\ x_1-x_2=K\cdot {\rm lcm}(m_1,m_2,\cdots,m_n)
$$
です。
これはまさに\(x_1\equiv x_2\ ({\rm mod}\ {\rm lcm}(m_1,m_2,\cdots,m_n))\)を表しています。

定理6.の証明終わり

実際に解いてみる

例１

$$
\begin{cases}
x\equiv 3\ ({\rm mod}\ 4)\\
x\equiv 20\ ({\rm mod}\ 25)\\
\end{cases}
$$
を解きます。

\(\gcd(4,25)=1\)ですので、解は存在し、その解\(x\)はある整数\(p,q\)を用いて
$$
x=25p+4q
$$
を満たします。

このとき、第一式より
$$
3\equiv 25p+4q\ ({\rm mod}\ 4)
$$
となり、\(25=4\times6+1\)から
$$
3\equiv p+0\ ({\rm mod}\ 4)
$$
だから、\(a\equiv 3\ ({\rm mod}\ 4)\)です。

一方で、同様にして
$$
20\equiv25p+4q\ ({\rm mod}\ 25)
$$
であり、
\begin{eqnarray}
&&20\equiv 25p+4q\ ({\rm mod}\ 25)\\
&&\Longleftrightarrow-5\equiv 0+4q\ ({\rm mod}\ 25)\\
&&\Longleftrightarrow4q\equiv -5\ ({\rm mod}\ 25)\\
&&\Longleftrightarrow24q\equiv -30\ ({\rm mod}\ 25)\\
&&\Longleftrightarrow-q\equiv-5\ ({\rm mod}\ 25)\\
&&\Longleftrightarrow q\equiv5\ ({\rm mod}\ 25)
\end{eqnarray}

求めたいのは\(x=25p+4q\)だから、\(p=3,q=5\)とすると\(x=25\times3+4\times5=95\)。
すなわち、\(x\equiv95\ ({\rm mod}\ 100)\)です。

例２

$$
\begin{cases}
x\equiv 4\ ({\rm mod}\ 15)\\
x\equiv 10\ ({\rm mod}\ 21)\\
\end{cases}
$$

これはサラッと解きます。

\(x=4+15t\equiv 10\ ({\rm mod}\ 21)\)により、\(15t\equiv6\ ({\rm mod}\ 21)\)です。
そして、\(5t\equiv2\ ({\rm mod}\ 7)\)より\(t\equiv6\ ({\rm mod}\ 7)\)です。
したがって、\(x\equiv4+15\times6=94\ ({\rm mod}\ 105)\)です。

皆様のコメントを下さい！

大学に入学して驚いたこと、そして結局慣れたことはありますか？
筆者は「え…数学の本ってこんなに高いの…？」と思いましたが、結局「専門書だしな。この本でマスターできると思えば高えよな。」と慣れてしまいました。

皆様はどうですか？
是非コメントで教えて下さい！

結

今回は、連立合同式の解の存在条件について解説しました。
条件は2つに分かれていて、

• 法が互いに素である場合(中国式剰余定理)
• 法が互いに素でない場合

です。

互いに素である場合は有名だと思いますが、素でない場合にも解が存在する場合があります。

次回は整数係数多項式の合同式について解説します。

乞うご期待！
質問、コメントなどお待ちしております！
どんな些細なことでも構いませんし、「定理〇〇の△△が分からない！」などいただければお答えします！
お問い合わせの内容にもよりますが、ご質問はおおよそ１週間以内にお答えします。
(難しかったらもう少しかかるかもしれませんが…)

初等整数論について、以下の書籍をオススメします！