1 元 1 次合同方程式の解の個数

$a$ と $m$ が互いに素である方程式に帰着させます

 前回にも述べたように、1 元 1 次合同方程式 と 2 元 1 次不定方程式は同等であって、その表現の仕方が異なるだけです。今回は前回までに得た定理等を用いて合同式による表現を見ていきます。まずは次の定理を証明します。

[定理 C9] $(a,\:m)=g$ とすると、1 元 1 次合同方程式
\[ax\equiv b\:\:(\mathrm{mod}\;m)\]は $g\:|\:b$ のときに限って解をもち、
\[a'x\equiv b'\:(\mathrm{mod}\;m')\]に帰着します。ただし $a=a'g,\:\:b=b'g,\:\:m=m'g$ です。

[定理 C9 の証明] $ax\equiv b\:\:(\mathrm{mod}\;m)$ なので
 
\[ax-b=my\:\:(y\in\mathbb{Z})\]
と表せます。すなわち
 
\[ax-my=b\tag{1}\]
となるので、前回記事の定理 C8

 $ax+by=c\:\:(a,b,c\:\in\mathbb{Z})$ が整数解をもつ $\Longleftrightarrow$ $(a,\;b)\:|\:c$

より、$(a,\;m)\:|\:b$ のときに限って解をもちます。また、
 
\[(a,\:m)=g,\:\:a=a'g,\:\:b=b'g,\:\:m=m'g\]
とおいて (1) に代入すると
 
\[a'x-m'y=b'\]
となるので、
 
\[a'x\equiv b'\:\:(\mathrm{mod}\;m')\]
を解くことに帰着します。(証明終)

 この定理は全ての 1 元 1 次合同方程式が $(a',\;m')=1$ すなわち $a'$ と $m'$ が互いに素となるような方程式に帰着できることを示しています。したがって、$(a,\;m)=1$ となるような合同方程式の解き方を知ることができれば、全ての 1 元 1 次合同方程式を解くことができるようになるということです。
 

1 元 1 次合同方程式の解の個数

 $(a,\;m)=1$ であれば解は1つ、そうでなければ $g$ 個の解をもつ、ということを述べているのが次の定理です。

[定理 C10] $ax\equiv b\:\:(\mathrm{mod}\;m)$ は $g\:|\:b$ のときに限って解をもち、
(1) $(a,\;m)=1$ であれば、唯1つの解をもちます
(2) $(a,\;m)=g\gt 1$ であれば $g$ 個の解をもち、
  その一般解は合同方程式を満たすある1つの解 $x_0$ を用いて
\[x=x_0+k\:\frac{m}{g}\:\:(k=0,\;1,\:\cdots ,\:m-1)\] で与えられます。

[定理 C10 の証明]
 $g\:|\:b$ のときに限って解をもつことは [定理 9] で証明しました。

(1) $ax\equiv b\:\:(\mathrm{mod}\;m)$ より
 
\[ax-my=b\:\:(y\in\mathbb{Z})\]
と表せます。$(a,\;m)=1$ なので 定理 C8

 $ax+by=c\:\:(a,b,c\:\in\mathbb{Z})$ が整数解をもつ $\Longleftrightarrow$ $(a,\;b)\:|\:c$

によって、この方程式には整数解が存在するので、それを $x_0$ とおくと一般解は
 
\[x=x_0+km\:\:(y\in\mathbb{Z})\]
と表すことができます。したがって
 
\[x\equiv x_0\:\:(\mathrm{mod}\;m)\]
となり、合同方程式の解は全て同じ剰余類に属することになります。

(2) $g\:|\:b$ なので、[定理 8] より $ax\equiv b\:\:(\mathrm{mod}\;m)$ は解をもちます。
  その中の解の1つを $x_0$ , 一般解を $x$ とすると
 
\[\begin{cases}ax\equiv b & (\mathrm{mod}\;m)\\[6pt]
ax_0\equiv b & (\mathrm{mod}\;m)\end{cases}\]
なので、
 
\[ax\equiv ax_0\:\:(\mathrm{mod}\;m)\]
が成り立ちます。ここで以前に証明した 定理 C5

 $ca\equiv cb\:(\mathrm{mod}\;m)$ が成り立つとき
 $(c,\:m)=g\gt 1\quad\Longrightarrow\quad a\equiv b\:\left(\mathrm{mod}\;\displaystyle\frac{m}{g}\right)$

を用いると、
 
\[x\equiv x_0\:\left(\mathrm{mod}\;\displaystyle\frac{m}{g}\right)\]
が成り立つことがわかります。したがって
 
\[x=x_0+k\:\frac{m}{g}\]
と表せますが、$\mathrm{mod}\;m$ で相異なる解となるのは
 
\[k=0,\;1,\:\cdots ,\:m-1\]
のときです ($k=0$ と $k=m$ は同じ類に属します)。よって解の個数は $g$ 個あり、その解は
 
\[x=x_0+k\:\frac{m}{g}\:\:(k=0,\;1,\:\cdots ,\:m-1)\]
で与えられます。(証明終)
 

1 元 1 次合同方程式の具体例

 簡単な合同方程式を解いてみます。
 
\[26x\equiv 30\:\:(\mathrm{mod}\;8)\tag{1}\]
 $g=(a,\;m)=(26,\;8)=2$ なので、
 
\[13x\equiv 15\:\:(\mathrm{mod}\;4)\tag{2}\]
という合同方程式に帰着します。ここで
 
\[4x\equiv 4\:\:(\mathrm{mod}\;4)\tag{3}\]
という合同式は当然成り立つので、(2) から (3) × 3 を引いて
 
\[x\equiv 3\:\:(\mathrm{mod}\;4)\]
という1つの解を得ます。これを $x_0$ とすると一般解は
 
\[x=x_0+k\:\frac{m}{g}\:\:(k=0,\;1,\:\cdots ,\:m-1)\]
で与えられます。$m/g=8/2=4$ なので $\mathrm{mod}\;8$ では
 
\[x\equiv 3,\:\:7\:\:(\mathrm{mod}\;8)\]
となります。これは剰余類 $C_3$ の要素 $x=3+8k$、および剰余類 $C_7$ の要素 $x=7+8k$ が全て $26x\equiv 30\:\:(\mathrm{mod}\;8)$ を満たすということです。

 ≫ 乗法的関数 ≫ 初等整数論入門講座

スポンサーリンク
スポンサーリンク
末尾広告
末尾広告

コメントをどうぞ

メールアドレスが公開されることはありません。

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください