整数の合同“≡”は“=”と同じ！？違いは？

本記事の内容

本記事は、整数の合同$\equiv$が等号$=$と“ほぼ”同じということを解説する記事です。

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

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

...

整数の合同“$\equiv$”と等号“$=$”は同じ！？

もちろん違います。
「そりゃあ異なる記号を使っているのだから、全く同じものなわけがない」と言われればそのとおりなのですが、実は

整数の合同$\equiv$と等号$=$は“ほぼ”同じ

なのです。

少々別の言い方をすれば、「整数の合同“$\equiv$”はおおよそ“$=$”と同様に扱うことができる。」ということです。

ミソなのは「おおよそ」の部分です。
では「おおよそ」の意味、すなわち、「$=$ではできるけれども$\equiv$でできないこと、または$=$と同様に扱うために必要な制約は何か？」ということについて解説します。

合同式の軽い復習

まずは、合同式を軽く復習します。
詳しくは【代数学の基礎シリーズ】初等整数論編その9を御覧ください。

合同式とは？

合同式

$m\in\mathbb{Z}\setminus\left\{0\right\}$とする。$a,b\in\mathbb{Z}$であり、$a-b$が$m$で割り切れる、すなわち $$ (\exists k\in\mathbb{Z})\ {\rm s.t.}\ a-b=km $$ となるとき、$a\equiv b\ ({\rm mod}\ m)$と書き、$a$と$b$は$m$を法として合同という。また、$a\equiv b\ ({\rm mod}\ m)$という形式の式を合同式という。

法$m$はよく自然数だと定められていますが、実は$0$でない整数であれば何でも良い、ということがミソなのでした。

合同式の意味

命題1.

$a,b\in\mathbb{Z}$、$m\in\mathbb{Z}\setminus\left\{0\right\}$とするとき、$a\equiv b\ ({\rm mod}\ m)$であることと、$a$および$b$を$m$で割った余りが等しいことは同値である。

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

命題1.は要するに何を言っているのか？ということですが、

$a\equiv b\ ({\rm mod}\ m)$と言われたらば、$a$を$m$で割った余りと$b$を$m$で割った余りが等しい。

ということでした。

整数の合同$\equiv$は$\mathbb{Z}$を有限個のグループに分ける。

命題2.

整数の合同$\equiv$は同値関係である。すなわち、任意の$a,b\in\mathbb{Z}$、任意の$m\in\mathbb{Z}\setminus\left\{0\right\}$に対して

反射律
対称律
推移律

が成り立つ。

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

先程、$a\equiv b\ ({\rm mod}\ m)$は「$a$を$m$で割った余りと$b$で割った余りが等しいという意味だ」と述べました。
命題2.から、同値類の知識を使うと、これは

$a\equiv b\ ({\rm mod}\ m)$と言われたらば、「$a$を$m$で割った余りと$b$を$m$で割った余りが等しい」というお意味で$a$と$b$は同じクラス(グループといっても良い)に属する。

と言いかえることができます。

※注意※(グループという言い回しについて)

数学、特に代数の分野には「群」という数学的な対象があります。
この「群」は英語では「group」です。
少々紛らわしいですが、ここでの「同じグループ」の”グループ”は群ではありません。

実は、この考え方は「整数の合同$\equiv$は$=$とほぼ同様に捉えることができる」という考え方につながる大事な視点です(後でもう一回書きます)。

整数の合同$\equiv$は、和・差・積については等号$=$と同じ性質を持つ

本題です。
なぜ整数の合同$\equiv$が$=$と“ほぼ”同じに扱うことができるのか？ですが、まずは和・差・積については等号$=$と同じ性質を持つのだ、ということについて述べます。

合同式の大事な性質(定理3.)の明示

定理3.

$a,a^\prime,b,b^\prime\in\mathbb{Z}$、$m\in\mathbb{Z}\setminus\left\{ 0\right\}$とする。このとき $$a\equiv a^\prime\ ({\rm mod}\ m),\quad b\equiv b^\prime\ ({\rm mod}\ m)$$ が成り立つならば、

$a\pm b\equiv a^\prime\pm b^\prime\ ({\rm mod}\ m)$,
$ab\equiv a^\prime b^\prime\ ({\rm mod}\ m)$

が成り立つ。
　一般に、$a\equiv a^\prime\ ({\rm mod}\ m)$、$b\equiv b\ ({\rm mod}\ m)$、$c\equiv c^\prime\ ({\rm mod}\ m)\cdots$で、また$f(x,y,z,\cdots)$が$x,y,z,\cdots$に関する整数を係数とする多項式であれば、 $$ f(a,b,c,\cdots\cdots)\equiv f(a^\prime,b^\prime,c^\prime,\cdots\cdots)\ ({\rm mod}\ m) $$ である。

定理3.の証明の前に、この定理3.が成り立つとはどういうことかということについてお話します。

「先に証明を知りたい！」という方は定理3.(合同式の大事な性質)の証明まで飛んでください。

定理3.が成り立つことの意味

定理3.が成り立つことの意味を一言で言えば、

整数の合同$\equiv$は、和(足し算)・差(引き算)・積(掛け算)については等号$=$と同じ性質を持つ。

ということです。
鋭い方はすでに察しが付いていると思いますが、定理3.は商(割り算)については一筋縄では行かないことを暗示しています。
そうです。
割り算については等号$=$とは同じように扱えないということが、“ほぼ”の意味だったのです(具体的な話は後述)。

定理3.(合同式の大事な性質)の証明

では、証明します。

定理3.の証明

(1.の証明)

仮定から、$a\equiv a^\prime\ ({\rm mod}\ m)$ですので、$a-a^\prime$は$m$の倍数です。
すなわち、
$$
(\exists k_a\in\mathbb{Z})\ {\rm s.t.}\ a-a^\prime=mk_a\tag{1}
$$
です。
さらに、仮定から$b\equiv b^\prime\ ({\rm mod}\ m)$ですので、$b-b^\prime$は$m$の倍数です。
すなわち、
$$
(\exists k_b\in\mathbb{Z})\ {\rm s.t.}\ b-b^\prime=mk_b\tag{2}
$$
です。
したがって、$(a+b)-(a^\prime+b^\prime)=(a-a^\prime)+(b-b^\prime)$は$m$の倍数です。
実際、(1)および(2)から
\begin{eqnarray}
(a+b)-(a^\prime+b^\prime)&=&(a-a^\prime)+(b-b^\prime)\\
&=&mk_a+mk_b\\
&=&m\left(k_a+k_b \right)
\end{eqnarray}
となるからです。

したがって、
$$
(a+b)-(a^\prime+b^\prime)=m\left(k_a+k_b \right)
$$
ですから、
$$
a+b\equiv a^\prime+b^\prime\ ({\rm mod}\ m)
$$
となります。

同様にしして、$(a-b)-(a^\prime-b^\prime)=(a-a^\prime)-(b-b^\prime)$も$m$の倍数です。
実際、(1)および(2)から
\begin{eqnarray}
(a-b)-(a^\prime-b^\prime)&=&(a-a^\prime)-(b-b^\prime)\\
&=&mk_a-mk_b\\
&=&m\left(k_a-k_b \right)
\end{eqnarray}
となるからです。

したがって、
$$
(a-b)-(a^\prime-b^\prime)=m\left(k_a-k_b \right)
$$
ですから、
$$
a-b\equiv a^\prime-b^\prime\ ({\rm mod}\ m)
$$
となります。

故に、1.の証明が完了です。

(2.の証明)

方針は1.と同じですが、式変形が少々テクニカルです。
証明したいことは$ab-a^\prime b^\prime$が$m$の倍数であるということです。

(1)および(2)から
\begin{eqnarray}
ab-a^\prime b^\prime&=&(a-a^\prime)b+a^\prime(b-b^\prime)\\
&=&mk_ab+a^\prime mk_b\\
&=&m\left( k_ab+a^\prime k_b\right)
\end{eqnarray}
となるため、$ab-a^\prime b^\prime$も$m$の倍数、すなわち
$$
ab\equiv a^\prime b^\prime\ ({\rm mod}\ m)
$$
となります。

特に、$ab\equiv a^\prime b^\prime\ ({\rm mod}\ m)$により、$b=b^\prime$の場合を考え、新たに$N=b=b^\prime$とすれば、
$$
Na\equiv Na^\prime\ ({\rm mod}\ m)
$$
が成り立ちます。

(これらの性質は因数の数に依存しないことの証明)

定理3.の証明自体は先程までの議論で終了ですが、定理3.から帰納的に以下がわかります。

$$
Na^\alpha b^\beta c^\gamma\cdots\cdots\equiv Na^{\prime^\alpha} Nb^{\prime^\beta} Nc^{\prime^\gamma}\cdots\cdots\ ({\rm mod}\ m)
$$
したがって、加え合わされる数がいくつあったとしても
$$
\sum Na^\alpha b^\beta c^\gamma\cdots\cdots\equiv \sum Na^{\prime^\alpha} Nb^{\prime^\beta} Nc^{\prime^\gamma}\cdots\cdots\ ({\rm mod}\ m)
$$
です。
故に、
$$
f(a,b,c,\cdots\cdots)\equiv f(a^\prime,b^\prime,c^\prime,\cdots\cdots)\ ({\rm mod}\ m)
$$

定理3.の証明終わり

なぜ、“ほぼ”なのだろうか？→割り算が単純にはできないから。

本題ですね。

主張の明示

なぜ“ほぼ”なのかというと、次が成り立つからです。

定理4.

$a,b,c\in\mathbb{Z}$、$m\in\mathbb{Z}\setminus\left\{ 0\right\}$、$ac\equiv bc\ ({\rm mod}\ m)$であるとする。このとき、$\gcd(c,m)=1$であれば、 $$ a\equiv b\ ({\rm mod}\ m) $$ である。
　一般に、$\gcd(c,m)=d$であれば、$m=dm^\prime$と書くとき、 $$ a\equiv b\ ({\rm mod}\ m^\prime) $$ である。

この定理4.が言わんとすることとしては、

割り算については、整数の合同$\equiv$を等号$=$と同じように扱うには条件が必要である

ということです。

主張の証明

定理4.の証明

仮定から$ac\equiv bc\ ({\rm mod}\ m)$であるため、$ac-bc=(a-b)c$は$m$の倍数です。
すなわち、
$$
(\exists k_1\in\mathbb{Z})\ {\rm s.t.}\ ac-bc=mk_1\tag{3}
$$
です。
まず、$\gcd(c,m)=1$の場合を考えます。

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

定理5.

$a,b,c\in\mathbb{Z}$とする。$\gcd(a,b)=1$で、かつ$bc$が$a$で割り切れるならば、$c$は$a$で割り切れる。

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

今、$ac-bc=(a-b)c$が$m$の倍数、すなわち
$$
(a-b)c=mk_1
$$
であり、かつ$\gcd(c,m)=1$であるため、定理5.から$a-b$は$m$の倍数です。
すなわち、
$$
(\exists k_2\in\mathbb{Z})\ {\rm s.t.}\ a-b=mk_2
$$
です。
したがって、$a\equiv b\ ({\rm mod}\ m)$が成り立ちます。

※注意※

この証明を見ると、割り算はしていないことがわかります。
しかし、$ac\equiv bc\ ({\rm mod}\ m)$かつ$\gcd(c,m)=1$ならば$a\equiv b\ ({\rm mod}\ m)$であるため、“形式的に”割り算をしているように見える、ということなのです。

一般に、$\gcd(c,m)=d$であれば、$d$は$c$の約数でもあり、なおかつ同時に$m$の約数でもあります。
故に、$m^\prime\in\mathbb{Z}\setminus\left\{ 0\right\}$および$c^\prime\in\mathbb{Z}$を用いて$m=dm^\prime$、$c^\prime=dc^\prime$と書けます。

今まで通りの記法に則れば、
\begin{eqnarray}
&&(\exists m^\prime\in\mathbb{Z}\setminus\left\{ 0\right\})\ {\rm s.t.}\ m=dm^\prime,\\
&&(\exists c^\prime\in\mathbb{Z})\ {\rm s.t.}\ c=dc^\prime
\end{eqnarray}
ということです。
このとき、$\gcd(c^\prime,m^\prime)=1$です。

実際、$\gcd(c^\prime,m^\prime)=l(\neq1)$とすると、
\begin{eqnarray}
&&(\exists \tilde{m}\in\mathbb{Z}\setminus\left\{ 0\right\})\ {\rm s.t.}\ m^\prime=l\tilde{m},\\
&&(\exists \tilde{c}\in\mathbb{Z})\ {\rm s.t.}\ c^\prime=l\tilde{c},\\
\end{eqnarray}
となります。
故に、
\begin{eqnarray}
m=dm^\prime=dl\tilde{m},\quad c=dc^\prime=dl\tilde{c}
\end{eqnarray}
となるから、$dl$は$c$と$m$の公約数です。
今、$l\neq0$かつ$l>0$($l$は最大公約数だから)であるため、$d<dl$です。
これは、$d$が$c$と$m$の公約数のうち最大のものである、ということに反します。
故に、$l=1$、すなわち、$\gcd(c^\prime,m^\prime)=1$です。

さて、今、$\gcd(c^\prime,m^\prime)=1$ですから、先程示したことから、$ac^\prime\equiv bc^\prime\ ({\rm mod}\ m^\prime)$ならば$a\equiv b\ ({\rm mod}\ m^\prime)$ということになります。
したがって、$\gcd(c,m)=d$ならば$m=dm^\prime$と書いたとき、
$$
a\equiv b\ ({\rm mod}\ m^\prime)
$$
となります。

定理4.の証明終わり

このように、合同式の両辺を共通の因数で割るときには、適切に法を変更しなければなりません。
これが“ほぼ”の意味なのです。

もしも法を変えないとするのなら、共通の因数が法と互いに素であるときに限って割り算が可能なのです。
これは、等号$=$にも似た性質があります。
というもの$ac=bc$から$a=b$を導くためには$c\neq0$であるという条件が必要だからです。

整数の合同$\equiv$と等号$=$の違いを具体例で見てみる。

具体例で確かめてみましょう。
以下、共通して
$$
3\equiv 1\ ({\rm mod}\ 2),\quad 8\equiv 4\ ({\rm mod}\ 2)
$$
および
$$
15\equiv 35\ ({\rm mod}\ 2),\quad 10\equiv 16\ ({\rm mod}\ 6)
$$
という合同式について考えます。

和

性質を再掲します。

定理3.

$a\pm b\equiv a^\prime\pm b^\prime\ ({\rm mod}\ m)$,
$ab\equiv a^\prime b^\prime\ ({\rm mod}\ m)$

これを確かめます。
つまり、$3+ 8\equiv 1+ 4\ ({\rm mod}\ 2)$を確かめます。

$3+8=11$であり、$11=2\times 5+1$であるため、$3+8$を$2$で割った余りは$1$です。
また、$1+4=5=2\times 2+1$であるため、$1+4$を$2$で割った余りも$1$です。
したがって、
$3+8\equiv 1+4\ ({\rm mod}\ 2)$が成り立ちます。

等号$=$についても見てみましょう。
確かに、$a=b$かつ$c=d$であれば、$a+c=b+d$ですので、和について整数の合同$\equiv$と等号$=$は同じく扱えます。

差

同じです。
つまり、$3-8\equiv 1-4\ ({\rm mod}\ 2)$を確かめます。

$3-8=-5$であり、$-5=2\times (-3)+1$であるため、$3-8$を$2$で割った余りは$1$です。
また、$1-4=-3=2\times (-2)+1$であるため、$1-4$を$2$で割った余りも$1$です。
したがって、
$3-8\equiv 1-4\ ({\rm mod}\ 2)$が成り立ちます。

等号$=$についても見てみましょう。
確かに、$a=b$かつ$c=d$であれば、$a-c=b-d$ですので、差について整数の合同$\equiv$と等号$=$は同じく扱えます。

積

$3\times8\equiv 1\times4\ ({\rm mod}\ 2)$を確かめます。

$3\times 8=24=2\times 12+0$により、$3\times8$を$2$で割った余りは$0$です。
また、$1\times 4=4=2\times 2+0$により、$1\times4$を$2$で割った余りは$0$です。
したがって、$3\times8\equiv 1\times4\ ({\rm mod}\ 2)$です。

等号$=$についても見てみましょう。
確かに、$a=b$かつ$c=d$であれば、$ac=bd$ですので、積について整数の合同$\equiv$と等号$=$は同じく扱えます。

商(これだけ注意)

まず、$15\equiv 35\ ({\rm mod}\ 2)$ならば$3\equiv 7\ ({\rm mod}\ 2)$を確かめます。
$3=2\times1+1$により、$3$を$2$で割った余りは$1$です。
そして$7=2\times6+1$により、$7$を$2$で割った余りは$1$です。
故に、$3\equiv 7\ ({\rm mod}\ 2)$です。

確かに、$3\times5\equiv 7\times5\ ({\rm mod}\ 2)$かつ$\gcd(5,2)=1$ですので、わり算ができています。

次に、$10\equiv 16\ ({\rm mod}\ 6)$ならば$5\equiv 8\ ({\rm mod}\ 6)$かを確かめます。
しかしながら、$5=6\times0+5$により、$5$を$6$で割った余りは$5$であり、$8=6\times1+2$により、$8$を$6$で割った余りは$2$となるから、$6$で割ったときの余りが一致しません。
故に、$5\not\equiv 8\ ({\rm mod}\ 6)$です。

確かに、$2\times5\equiv 2\times8\ ({\rm mod}\ 6)$かつ$\gcd(2,6)=2\neq1$ですので、わり算ができていません。
そして、$6=2\times3$であることに注目すると、
\begin{eqnarray}
&&5=3\times1+2\\
&&8=3\times2+2
\end{eqnarray}
となり、$3$で割った余りが一致しているため、法を$3$に取り替えれば、わり算ができています。

等号$=$についても見てみましょう。
$ac=bc$かつ$c\neq0$であれば、$a=b$です。
確かに$c\neq0$という条件が付きますが、「法を取り替える」という操作に対応する操作がありません。
故に商について整数の合同$\equiv$と等号$=$は同じく扱うことはできません。

整数の合同$\equiv$と等号$\equiv$に対する大事な視点

これは整数の合同$\equiv$に限らない話なのですが、数学には“商”という概念があります。
“商”集合やら“商”群やらといろいろあります。

筆者が学部、修士とお世話になった大数学者曰く

商の概念への理解が、数学において最も重要である。特に商集合の概念の理解が最重要である。

だそうです。
筆者はこの言葉を100%理解したとは言えませんが、その片鱗はわかります。

今回扱っている整数の合同$\equiv$にも商の概念が見え隠れしています。
以前述べたとおり、整数の合同$\equiv$は同値関係です。
同値関係を定めることができる集合は、その同値関係に対する同値類でもってグループ分け(クラス分け、仲間分け)できます。
つまり、今回の場合においては、$\mathbb{Z}$をグループ分けできるという話です。

これはどういうことなのか？と。
それは

同じグループに属するモノは“同じものである”と捉える。

ということなのです。

序盤で述べましたが、$a\equiv b\ ({\rm mod}\ m)$は

と捉える事ができるのでした。
先程の「同じグループに属するモノは“同じものである”」という視点を入れれば、

$a\equiv b\ ({\rm mod}\ m)$は、「$m$で割った余りが等しい」という意味で、$a$と$b$は同じモノと捉えるという意味。

ということなのです。
そして、今回紹介した定理3および定理4.から、整数の合同$\equiv$は確かに等号$=$と似た扱いができるということからも「同じモノと捉える」ということの正当性がわかります。

この視点は重要です。
厳密に言えば異なるものでも、うまく世界を定めれば(考える範囲を限定すれば)同じモノと捉えることができるということなのです。

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

先程筆者は学部と修士の頃に大変お世話になった大数学者からの言葉を紹介しました。

皆様はこれまで、小中高大であらゆる”先生”と出会ってきたかと思います。
その中で、心に残っている言葉はありますか？

ぜひコメントで教えて下さい！

結

今回は、整数の合同$\equiv$が等号$=$と“ほぼ”同じということを解説しました。
“ほぼ”の意味としては、わり算が一筋縄では行かないということでした。

つまり、正直に割り算はできず、割り算をするには条件が必要ということです。

今や高校数学で学ぶ整数の合同、合同式です。
そこで「整数の合同$\equiv$と等号$=$は同じように扱えるよ」と習うと思います。
では、「全く同じでない理由は？」というところに今回は焦点を当てました。

次回は一次の合同不定方程式について解説します。

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

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