本記事の内容
本記事は「一次合同式の解の存在条件」について解説する記事です。
本記事を読むにあたり、合同式について知っている必要があるため、以下の記事も合わせてご覧ください。
「解く」とは？
端的に言えば、「合同式を解く」というのは
です。
これは、合同式に限らず方程式についてもそうです。
要するに「未知数を求めること」が「解く」ということです。
「一次合同式を解く」とは？
今の話を厳密に書くと以下になります。
合同式を解く
\(f(x)\)が整数係数の多項式であるとき、合同式 $$ f(x)\equiv 0\ ({\rm mod}\ m) $$ を満たす未知の整数\(x\)を求めることを合同式を解くという。合同式は、一般的な方程式のようには解けない。
例えば、次の問題を考えてみます。
「んなもん\(x=2\)でしょ。」となるでしょう。
勿論正解です。
解き方は1つだけではありませんが、両辺を\(2\)で割って\(x=2\)と求めるのが一般的でしょう。
(勿論、\(2\)に何かを掛けて\(4\)になるんだから\(x=2\)だ、と解いてもOKです)
そして、この例の本質的な意味は
ということです。
では、次はどうでしょう。
例1.と同様に「\(5x\)と\(3\)を\(5\)で割れば…あれ？」となるのではないでしょうか。
仮に割ったとしても、“形式的に”\(\displaystyle x\equiv \frac{3}{5}\)となりますが、そもそも「合同式を解く」というのは「未知の“整数”\(x\)を求めること」だったわけですので、\(\displaystyle\frac{3}{5}\not\in\mathbb{Z}\)ですから、この方法ではダメです。
そして、前回解説したように、合同式に対して割り算は一筋縄では行かないのでした。
定理3.
\(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) $$ である。
定理3.の証明は【代数学の基礎シリーズ】初等整数論編 その10を御覧ください。
正直に解いてみる。
では、合同式の性質を使って、正直に解いてみましょう。
\(5x\equiv 3\ ({\rm mod}\ 7)\)なのですから、
$$
(\exists k\in\mathbb{Z})\ {\rm s.t.}\ 5x-3=7k\tag{1}
$$
となります。
これを満たすような\(x\in\mathbb{Z}\)を求めたいわけです。
ただ、「求めたい」は良いのですが、そもそも解が存在するのか？ということから初めなければなりません。
(1)を変形すると
$$
5x-7k=3
$$
となります。
要するに、これを満たすような整数\(x,k\)が存在するか？ということです。
これは存在します。
なぜなら、次が成り立っているからです。
定理4.
一次の不定方程式 $$ ax+by+cz=k\quad (a,b,c,k\in\mathbb{Z}) $$ が整数解を持つための必要十分条件は、\(k\)が\(d=\gcd(a,b,c)\)で割り切れることである(変数の数は任意)。定理4.の証明は【代数学の基礎シリーズ】初等整数論編 その6を御覧ください。
確かに、\(\gcd(5,-7)=1\)であり、\(3\)は\(1\)で割り切れるから、定理4.により\(5x-7k=3\)は整数解を持つ、すなわち\(5x-7k=3\)を満たす整数\(x,k\)が存在することがわかります。
さて、解が存在することはわかりました。
では、具体的な解は何でしょうか。
(1)を再度変形すれば、
$$
5x=7k+3
$$
となります。
これは、「\(5x\)は\(7\)で割ると\(3\)余る」と捉えることができます。
つまり、この場合は「\(5\)に何かを掛けて\(7\)で割ると\(3\)余るような整数を求めよ」ということになるわけです。
鋭い方は「おや？」となるのではないでしょうか。
そうです。
解は唯一つではありません。
\(x=2\)とすると、\(5\times2=10=7\times1+3\)となりますから、\(x=2\)は解です。
さらに、\(x=9\)としても\(5\times9=45=7\times6+3\)となりますから、\(x=9\)も解です。
他にもたくさんあります。
このように、解が一つに定まりません。
要するに、\(x\equiv2\ ({\rm mod}\ 7)\)を満たす整数であれば、何でも良いのです。
これが一般的な方程式との違いです。
「合同式を解く」とは？
結局の所、合同式は先程の例のように、解が一つの整数に定まるわけではありません。
より一般に、
$$
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)
$$
となります。
なぜなら、次が成り立つからです。
定理5.
\(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) $$ である。
定理5.の証明は【代数学の基礎シリーズ】初等整数論編 その10を御覧ください。
すなわち、\(m\)を法として\(x_0\)と同じ同値類(整数の合同\(\equiv\)は同値関係だから)に含まれる整数はすべて(\(\ast\))の解なのです。
したがって、合同式を解くというのは、
ということになるわけです。
「類を求めること」なので、実は虱潰しに解を求めることができます。
なぜなら、\(m\)を法とすれば、\(\mathbb{Z}\)はちょうど\(m\)個の類に分けられるからです。
つまり、\(\mathbb{Z}\)は\(m\)で割り切れるグループ、\(1\)余るグループ、\(2\)余るグループ、\(\cdots\)、\(m-1\)余るグループの\(m\)個の類に分けられます。
したがって、これらを1つずつ当てはめてみれば良いわけなのです。
要するに、手数さえ厭わなければ、合同式を解くことができるのです。
一次合同式の解の存在条件
では、一時の場合について、合同式の解の存在条件を述べます。
定理6.
一次合同式 $$ ax\equiv b\ ({\rm mod}\ m) $$ は\(\gcd(a,m)=1\)なるときは、1つの解を持つ。\(\gcd(a,m)=d>1\)であるときは、\(b\)が\(d\)で割り切れるときに限って解を持つ。その解の数は\(d\)である。ただし、解の数は\(m\)を法としての類の関してである。解の個数ですが、これは\(m\)を方とした同値類の数です。
定理6.の証明
①\(\gcd(a,m)=1\)のとき
\(x\)に対して、\(m\)を法とした\(m\)個の剰余類(同値類)からそれぞれ1つずつ整数を任意に選び、
$$
x_1,\ x_2,\cdots,x_m\in\mathbb{Z}
$$
と書いたとしましょう。
これを\(m\)を法とする剰余系といいます。
このとき、
$$
ax_1,\ ax_2,\cdots,ax_m\in\mathbb{Z}
$$
もまた、\(m\)を法とする剰余系です。
すなわち、\(m\)個の剰余類から一つずつ任意に整数を選んだものとなっているわけです(ただし、\(x_i\)と\(ax_i\)が同じ剰余類に属するとは限りません)。
実際、\(ax_h\equiv ax_k\ ({\rm mod}\ m)\)となるのは、\(a(x_h-x_k)\)が\(m\)で割り切れるときであり、仮定から\(\gcd(a,m)=1\)なので、\(x_h\equiv x_k\ ({\rm mod}\ m)\)です。
これは\(h=k\)のときに限ります。
ただし、ここで以下の事実を使いました。
定理7.
\(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) $$ である。
定理7.の証明は【代数学の基礎シリーズ】初等整数論編 その10を御覧ください。
したがって、\(b\)がどんな整数であれ、\(x_1,\cdots,x_m\)の中に唯一
$$
ax\equiv b\ ({\rm mod}\ m)
$$
となるような\(x\in\mathbb{Z}\)が存在します。
②\(\gcd(a,m)=d>1\)のとき
$$
ax\equiv b\ ({\rm mod}\ m)\tag{1}
$$
に解があったとすると、
$$
(\exists y\in\mathbb{Z})\ {\rm s.t.}\ ax-b=my
$$
です。
故に、定理4.から\(b=ax-my\)は\(d=\gcd(a,m)\)で割り切れなければなりません。
\(b\)が\(d=\gcd(a,m)\)で割り切れるとすると、\(d=\gcd(a,m)\)だから、\(a\)も\(m\)も\(d\)の倍数であることに注意して
$$
a=da^\prime,\quad m=dm^\prime,\quad b=db^\prime
$$
と書くことができます。
このとき(1)は
$$
a^\prime x\equiv b^\prime\ ({\rm mod}\ m^\prime)\tag{2}
$$
となります。
なぜなら、定理3.が成り立っているからです。
ここでは\(\gcd(a^\prime,m^\prime)=1\)だから(初等整数論編 その10の道中を参照)、(2)を満たす\(x\)は\(m^\prime\)を法としての1つの剰余類です。
それを\(x\equiv x_0\ ({\rm mod}\ m^\prime)\)とすると、(2)の解は
$$
x=x_0+m^\prime\quad (t\in\mathbb{Z}) t\tag{3}
$$
で得られます。
\(t\)の2つの値\(t_1\)および\(t_2\)について、これらが\(m\)を法として合同になるのは\(m^\prime(t_1-t_2)\)が\(m\)で割り切れるとき、すなわち\(t_1-t_2\)が\(d\)で割り切れるときに限ります。
故に、(3)において\(t=0,1,2,\cdots,d-1\)なる値を与えれば、\(m\)を法としての(1)のすべての解が得られるということになります。
したがって、解の数は\(d\)個です。
定理6.の証明終わり
実際に解いてみる。
次の一次合同式を解いてみましょう。
\(26x\equiv 1\ ({\rm mod}\ 57)\)
まず、解が存在するかどうかですが、\(\gcd(26,57)=1\)ですので、1つの解が存在します。
それを\(x\)と書きます。
虱潰しに\(x=0,1,2,\cdots,56\)まで代入しても解は求まりますが、面倒です。
目標は、なんとかして\(x\equiv\)の形に持っていくことです。
\(26\)の部分が\(57\)に近ければ、\(26\)の部分をより小さい整数で表すことができます。
「ん？」となるかと思いますので実際にやってみます。
\(57=26\times2+5\)ですので、\(26\)に\(2\)を掛けると値が近くなります。
故に、
$$
52x\equiv 2\ ({\rm mod}\ 57)
$$
という式が得られます(定理5.)。
すると、どんな整数\(x\)に対しても
$$
52x+5x=57x\equiv 0\ ({\rm mod}\ 57)
$$
なわけですから、
$$
52x\equiv -5x\ ({\rm mod}\ 57)
$$
です。
したがって、
$$
-5x\equiv 2\ ({\rm mod}\ 57)
$$
を満たすような\(x\in\mathbb{Z}\)を求めれば良いわけです。
ここで、\(-5x\equiv 2\ ({\rm mod}\ 57)\)の両辺に\(5\)を掛けると
$$
-25x\equiv 10\ ({\rm mod}\ 57)
$$
です。
元の式の両辺と足し合わせることで、
$$
26x-25x\equiv 1+10\ ({\rm mod}\ 57)
$$
となるから、\(x\equiv 11\ ({\rm mod}\ 57)\)が答えとなるわけです。
皆様のコメントを下さい！
たまたまデカルトを調べていたときに、「困難は分割せよ。」という名言を見つけました。
これを見たときに「これって、数学で言うところの場合分けのことか」と思い至りました。
難しい問題は、いっぺんにすべてを考えるからわからないのであって、細かく場合で分けて、それぞれの場合についてのみ考えるということを繰り返すことで解決を図る、ということなのかなと思いました。
皆様の好きな名言を是非コメントで教えて下さい！
結
今回は、一次合同式の解の存在条件について解説しました。
合同式は普通の方程式と違って解が1つに定まるとは限りません。
そして、方程式のように「割る」という操作が単純にはできません。
さらに、なによりもまず「そもそも解が存在するのだろうか？」ということから吟味しなければなりません。
次回は合同式の連立方程式について解説します。
乞うご期待！
質問、コメントなどお待ちしております！
どんな些細なことでも構いませんし、「定理〇〇の△△が分からない！」などいただければお答えします！
お問い合わせの内容にもよりますが、ご質問はおおよそ１週間以内にお答えします。
(難しかったらもう少しかかるかもしれませんが…)
初等整数論について、以下の書籍をオススメします！
コメントをする