合同式の両辺を割ることのできる条件

6 を法とする合同方程式

 $\mathrm{mod}\;6$ の乗算表は次のようになります。

 Excelで作成した合同式mod6乗算表

 比較のために $\mathrm{mod}\;7$ 乗算表も再掲しています。
 $\mathrm{mod}\;7$ 乗算表の各行では $0$ から $6$ の数字が一通り現れていますが、$\mathrm{mod}\;6$ 乗算表では同じ数が周期的に現れる行が存在しています。するとたとえば
 
\[2x\equiv 4\:(\mathrm{mod}\;6)\]
という合同方程式は
 
\[x\equiv 2,\:5\:(\mathrm{mod}\;6)\]
という複数の解をもつことになります。

 合同式2x≡4の解

 また $2x\equiv 5\:(\mathrm{mod}\;6)$ という合同方程式を解こうとしても、$2$ に乗じて $5$ になるような数は乗算表のどこにも見当たらないので「解なし」ということになります。このように合同方程式では、選んだ法によって解が存在しなかったり不定であったりする場合があるのですが、そこにはもちろん法則があるので、これから丁寧に調べていきます。
 

合同式の両辺を割ることのできる条件

 そこでまず今回の記事では普通の等式と同じように 合同式の両辺を同じ数で割ってもよいのかどうか を考えます。先ほどの例の
 
\[2x\equiv 4\:(\mathrm{mod}\;6)\]
という合同方程式で両辺を $2$ で割って
 
\[x\equiv 2\:(\mathrm{mod}\;6)\]
としてしまうと 2 つあるうちの一方の解しか得られないので明らかに誤りです。しかし法を $7$ に変えて
 
\[2x\equiv 4\:(\mathrm{mod}\;7)\]
という合同方程式であれば、
 
\[x\equiv 2\:(\mathrm{mod}\;7)\]
として全く問題ありません。選んだ法によって、どうしてこのような違いが生じてしまうのでしょう。それについて述べているのが次の定理です。

[定理 C5] $ca\equiv cb\:(\mathrm{mod}\;m)$ が成り立つとき
(1) $(c,\:m)=1$ であれば $a\equiv b\:(\mathrm{mod}\;m)$
(2) $(c,\:m)=d\gt 1$ であれば $a\equiv b\:\left(\mathrm{mod}\;\displaystyle\frac{m}{d}\right)$

[定理 C5 の証明] 証明には以前に学んだ 定理 A11
 
\[(a,\:b)=1,\quad a\:|\:bc\quad \Longrightarrow\quad a\:|\:c\]
を用います。$ca\equiv cb\:(\mathrm{mod}\;m)$ なので、
 
\[m\:|\:c(a-b)\]
 $(c,\:m)=1$ のときは定理 A11 より
 
\[m\:|\:a-b\quad\therefore a\equiv b\:(\mathrm{mod}\;m)\]
 $(c,\:m)=d\gt 1$ のとき
 
\[c=dc',\quad m=dm'\]
とおくと $(c',\:m')=1$ なので
 
\[\begin{align*}dm'&\:|\:dc'(a-b)\:(\mathrm{mod}\;m)\\[6pt]
m'&\:|\:c'(a-b)\:(\mathrm{mod}\;m)\\[6pt]
m'&\:|\:a-b\:(\mathrm{mod}\;m)\\[6pt]
&\therefore a\equiv b\:(\mathrm{mod}\;m)\end{align*}\]
となります。(証明終)

 この定理は $c$ と $m$ が互いに素である場合のみ、両辺を $c$ で割っても合同関係が維持されることを述べています(互いに素でなければ法を $m/d$ に変えて合同式が成り立ちます)。再び先ほどの
 
\[2x\equiv 4\:(\mathrm{mod}\;6)\]
という合同方程式を考えると、
 
\[(c,\:m)=(2,\:6)\neq 1\]
なので両辺を $2$ で割ることはできません。しかし
 
\[2x\equiv 4\:(\mathrm{mod}\;7)\]
であれば、
 
\[(c,\:m)=(2,\:7)=1\]
ですから、両辺を $2$ で割って
 
\[x\equiv 2\:(\mathrm{mod}\;7)\]
とすることができます。一般に
 
\[cx\equiv ca\:(\mathrm{mod}\;m)\]
という合同方程式を考えたときに、$m$ が素数でれば、どのような $c$ とも互いに素な関係にあるので、合同方程式の両辺を $c$ で割ることができます。一方で $m$ が合成数であるときは、$m$ と互いに素ではない $c$ については、合同方程式の両辺を $c$ で割ることはできないのです。

 ≫ 不定方程式 ax + by = (a, b) ≫ 初等整数論入門講座

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

コメントをどうぞ

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

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