連立一次合同式


1　方程式がすべて同じ法のとき

$\hspace{5em}(合同式や法については$合同式を参照)

　

$pが素数ならば、R(p)=Z/pZ=\{0,1,2,\cdots ,p-1\} はpを$
$法として体となります。$
$例えば、R(5)の演算表は右表のとおりです。$

$R(p)は体ですから、連立一次方程式はごく普通に解く$
$ことができます。$

$例1 \quad 5を法として、次の連立方程式を解いてみましょう。$
\[ \hspace{1em} \left\{ \begin{array}{l} 2x+y \equiv 1 \hspace{5em}(1)\\ x+2y \equiv 4 \hspace{5em}(2)\\ \end{array} \right. \]
$\quad (1) \times 2 より$
$\qquad 4x+2y \equiv 2 \hspace{7em}(3)$
$\quad (3)-(2)$
$\qquad 3x \equiv -2 \equiv 3 \ \ より　x \equiv 1$
$\quad (1)に代入して　y \equiv -1 \equiv 4$


2　方程式ごとに異なる法のとき


$例2$
\[ \hspace{1em} \left\{ \begin{array}{l} x \equiv 2 \quad (mod \ \ 5) \hspace{5em}(1)\\ x \equiv 3 \quad (mod \ \ 8) \hspace{5em}(2)\\ \end{array} \right. \]
$(1)の解は　x=2,7,12,17,22,27,\cdots $

$(2)の解は　x=3,11,19,27,\cdots $

$(1),(2)をともに満たす数は \ \ x \equiv 27$
$したがって　x \equiv 27 \quad (mod \ \ 40)$


$具体的な問題なのでこの解法でよいが、一般化できない。$
$そこで、次のように問題設定してみましょう。$

問題１　連立2元方程式


$整数m,nは互いに素として$
\[ \hspace{1em} \left\{ \begin{array}{l} x \equiv a \quad (mod \ \ m) \hspace{6em}(1)\\ x \equiv b \quad (mod \ \ n) \hspace{6em}(2)\\ \end{array} \right. \]
$M=mm 、M_1=\cfrac{M}{m},\ M_2=\cfrac{M}{n}\ \ とし$

$M_1u_1=1\ \ (mod \ \ m),\ \ M_2u_2=1\ \ (mod \ \ n) \ \ となるように整数u_1,u_2を選び$
$\hspace{3em}(u_1,u_2は剰余体R(m),R(n)におけるM_1,M_2の逆元のこと)$

$\quad x=M_1x_1+M_2x_2 \ \ とおくと$

$mod \ \ m \ \ について$

$\quad M_2=m \ \ だから \quad x \equiv M_1x_1 \equiv a$
$\quad 両辺にu_1 をかけて \quad M_1x_1u_1 \equiv au_1$
$\quad (M_1u_1)x_1 \equiv au_1 \quad \therefore x_1 \equiv au_1$

$同様にして　mod \ \ n \ \ について \quad x_2 \equiv bu_2$

$したがって　法 \ \ mn \ \ として\ \ x \equiv M_1au_1+M_2bu_2$


$この方法で、例2を解いてみましょう。$

$x=8x_1+5x_2 \ \ とおくと$

(i)$\ \ \mod \ \ 5\ \ について$
$\quad x \equiv 8x_1 \ \ だから　8x_1 \equiv 2 \equiv 32 \quad \therefore x_1=4$

(ii)$\ \ \mod \ \ 8\ \ について$
$\quad x \equiv 5x_2 \ \ だから　5x_2 \equiv 3 \equiv 35 \quad \therefore x_2=7$

$\quad 法 \ \ 40 \ \ として \ \ x=8 \times 4+5 \times 7=67 \equiv 27$


問題２　連立3元方程式


$整数l,m,nはどの2つも互いに素として$
\[ \hspace{1em} \left\{ \begin{array}{l} x \equiv a \quad (mod \ \ l) \hspace{5em}(1)\\ x \equiv b \quad (mod \ \ m) \hspace{4em}(2)\\ x \equiv c \quad (mod \ \ n) \hspace{5em}(3)\\ \end{array} \right. \]
$問題1にならって$

$\quad x=mnx_1+nlx_2+lmx_3 \ \ とおき、与えられた方程式からx_1,x_2,x_3 を求めればよい。$

$例3$
\[ \hspace{1em} \left\{ \begin{array}{l} x \equiv 1 \quad (mod \ \ 3) \hspace{5em}(1)\\ x \equiv 2 \quad (mod \ \ 5) \hspace{5em}(2)\\ x \equiv 3 \quad (mod \ \ 7) \hspace{5em}(3)\\ \end{array} \right. \]
$x=5 \times 7x_1+7 \times 3x_2+5 \times 3x_3 \ \ とおくと$

(i)$\ \ mod \ \ 3 \ \ について$
$\quad x \equiv =35x_1 \equiv 1$
$\quad 2x_1 \equiv 1 \equiv 4$
$\quad \therefore x_1=2$

(ii)$\ \ mod \ \ 5 \ \ について$
$\quad x \equiv 21x_2 \equiv 2$
$\therefore x_2 \equiv 2$

(iii)$\ \ mod \ \ 7 \ \ について$
$\quad x \equiv 15x_3 \equiv 3$
$\quad \therefore x_3 \equiv 3$

$したがって、3 \times 5 \times 7=105 \ \ を法として$
$\quad x=35 \times 2+21 \times 2+15 \times 3=157 \equiv 52$


$なお、この例3のように、法3,5,7についての問題は、和算家　吉田光由の塵劫記にとりあげられていますが、$
$法の積が105になることから百五げん（減あるいは間とかかれる)算といわれています。$

$百五げん算の例$
$\quad 碁石がいくつかる。7個ずつとっていくと2個残り、5個ずつとっていくと1個残り、３個ずつとっていくと$
$\quad 2個残るとき、碁石はいくつあったか。$


問題３　連立n元方程式



$どの2つの法も互いに素として$
\[ \hspace{1em} \left\{ \begin{array}{l} x \equiv a_1 \quad (mod \ \ m_1) \hspace{5em}(1)\\ x \equiv a_2 \quad (mod \ \ m_2) \hspace{5em}(2)\\ \hspace{2em}\vdots\\ x \equiv a_n \quad (mod \ \ m_n) \hspace{5em}(n)\\ \end{array} \right. \]
$M=m_1m_2 \cdots m_n \ \ とし、M_1=\cfrac{M}{m_1},\ M_2=\cfrac{M}{m_2},\ \cdots , \ M_n=\cfrac{M}{m_n} \ \ とおく$

$M_1u_1=1\ \ (mod \ \ m_1),\ \ M_2u_2=1\ \ (mod \ \ m_2),\ \ \cdots , \ \ M_nu_n=1\ \ (mod \ \ m_n) $
$となるように整数u_1,u_2,\cdots ,u_n を選び$

$\quad x=M_1x_1+M_2x_2+\cdots +M_nx_n \ \ とおくと$

$mod \ \ m_1 \ \ について$
$\quad M_2,\ M_3,\ \cdots,\ M_n \ にはm_1が含まれているから$
$\quad x \equiv M_1x_1 \equiv a_1$
$\quad M_1u_1x_1 \equiv a_1u_1$
$\quad \therefore x_1 \equiv a_1u_1$

$同様にして　x_k \equiv a_ku_k \quad (k=1,2, \cdots n)$

$したがって　法 \ \ M \ として \ \ x \equiv M_1a_1u_1+M_2a_2u_2+\cdots +M_na_nu_n $


3　方程式にいくつかの変数が含まれルとき


$例$
\[ \hspace{1em} \left\{ \begin{array}{l} x+y \equiv 1 \ \quad (mod \ \ 2) \hspace{5em}(1)\\ 2x+y \equiv 2 \quad (mod \ \ 3) \hspace{5em}(2)\\ \end{array} \right. \]
$この手の問題は合同式というより、むしろ不定方程式を解くことになります。$
$(1),(2)はk,lを整数として$
\[ \hspace{1em} \left\{ \begin{array}{l} x+y=1+2k \quad (mod \ \ 2) \hspace{5em}(3)\\ 2x+y=2+3l \quad (mod \ \ 3) \hspace{5em}(4)\\ \end{array} \right. \] $とおけますから$
$(4)-(3)より$
$\quad x=1-2k+3l$
$(3)に代入して$
$\quad y=2k+1-(1-2k+3l)=4k-3l$



ページの先頭へ↑




メインメニュー　に戻る