一次不定方程式 ax+by=c の整数解【環論への布石】
一次不定方程式 ax+by=c の整数解について、特殊解と一般解の説明から始めます。
そして、図形と方程式の観点からベクトル方程式を用いて可視化します。
その後で、大学の環論入門の単項イデアル整域という背景を明らかにしています。
高校の整数分野で具体的に慣れつつ、大学の数学へとつながれば幸いです。
大学の数学の内容は抽象的なので、高校の数学で地ならしをしてから、環論の内容へと踏み込みます。
高校生の方も、高校の発展内容として、イデアルを知るということで気分展開に最後に述べる単項イデアル整域の内容をご覧頂ければと思います。
一次不定方程式 :特殊解と一般解
【一次不定方程式】
a, b, c を整数とし、
方程式ax + by = c の整数解の組 (x, y) について考えます。
はじめに与えられた定数 a, b, c は整数です。そして、x と y に代入する数は整数に限定されているという状況です。
「ax + by = c」という方程式は、中学で習ったように、一次関数を定めます。
そして、x と y に整数しか代入できないということから、この関数の x の定義域は整数全体の部分集合となっています。
具体的に、a, b, c をそれぞれ 6, 8, 2 として、シンプルな一次関数を表す方程式で様子を見ることにします。
例えば、6x + 8y = 2
未知数 x と y が二個であるのに対して、方程式が一個しかない状況です。
濃度と食塩水などで扱った連立方程式と違って、x と y の組が存在したとしても、一通りとは限りません。
一般に、a, b, c にランダムに整数を当てはめた不定方程式だと整数解が一つも存在しないということが起こります。
しかし、6x + 8y = 2 については、整数解の組 (x, y) が存在します。しかも、無限通りの整数解が存在します。
中学で学習した一次関数のグラフと、ベクトル方程式を用いた図形と方程式の観点で、より詳しく説明します。
特殊解という座標から
6x + 8y = 2 の解を一つ、直観でも何でも良いので、一つ見つけます。
(x, y) = (3, －2) を代入すると、方程式の左辺と右辺の値がともに 2 となって等しいので、これは整数解の一つです。
このグラフ上の具体的な 1 点 (3, －2) を表している x = 3, y = －2 が特殊解です。
さらに、6x + 8y = 2 という直線グラフ上の点で、x 座標と y 座標の両方ともが整数となっている格子点をすべて見つけたいと考えます。
この x 座標と y 座標がどちらも整数になっている点を表すパラメータを使って一般的に表すものが一般解ということになります。
6x + 8y = 2 の一般解は、中学数学ですぐに分かります。
y = －3/4x + 1/4 ですから、
右に 4 進むと下に 3 進むという状況です。
この変化の割合が一定であることから、
特殊な点 (3, －2) から右に 4k 進み 下に 3k 進んだ点が直線上の格子点です。
※ ただし、パラメータ k には整数のみを代入することとします。
直線上の任意の点を P(x, y) とすると、
x = 3 + 4k, y = －2 － 3k
直線上の任意の点 P(x, y) の座標が、
(3 + 4k, －2－3k) と表されます。
k に具体的な整数を代入すると、具体的な直線上の格子点の座標が表示されます。
x = 3 + 4k, y = －2 － 3k という一般解が分かると、パラメータ k に具体的な整数を代入するだけで、直線上の格子点の座標を具体的に表示できるということになります。
k = 2 のとき、上の図で P(11, －8) です。
ここまでが、文系数学用の考察です。ここから、理系の方向けに、ベクトルを用いて述べておきます。
変化の割合と方向
y = y = －3/4x + 1/4 という直線の傾きは一定で、右に 4 進むと下に 3 進むという方向です。
この方向ベクトルが (4, －3) です。
特殊解 x = 3, y = －2 から、
直線上の定点が A(3, －2) です。
特殊解から定まる定点を原点を中心とする位置ベクトルで表し、方向ベクトルで調整することで、直線上の任意の格子点 P を表すことができます。
ベクトル OA に方向ベクトル AB の k 倍を加えると、ベクトル OP となるということです。
式で x 成分と y 成分を表したものが、
x = 3 + 4k, y = －2 － 3k
k = 2 だと、ベクトル AB の長さの 2 倍分だけ右に動くので、P(11, －8) となっていたわけです。
一次不定方程式 :特殊解を求める
6x + 8y = 2 の一般解を求めるときに、先に特殊解を求めていました。
特殊解が分かれば、中学の数学で簡単に一般解をパラメータを一個使うことで表すことができます。
そのため、特殊解を求める方法が知りたいところです。
そこで、少し論理を使います。
はじめに与えらえた整数 a, b, c について、
ax + by = c の整数解の組 (x, y) が存在するということの必要条件を求めてみます。
※ ただし、a も b も 0 ではないとします。
互除法を用いることで、a と b の最大公約数 d が得られます。
a = dv, b = dw （v と w は整数）とすると、
c = ax + by = dsx + dty = d(vx +wy)
vx + wy は整数なので、c は d の倍数ということになります。
したがって、一次不定方程式の整数解が存在するときに、右辺の c は、a と b の最大公約数の倍数ということが分かりました。
では、実際に最大公約数を求めることから、特殊解を求めてみます。
実際に求める
8 = 1 × 6 + 2, 6 = 3 × 2 + 0
互除法から、6 と 8 の最大公約数が 2 と分かりました。
最大公約数を求めたときに出てきた等式たちを使って、右辺が 2 となる等式をつくります。
そのときに、6 に掛けられている整数と 8 に掛けられている整数が、整数解となります。
この例だと、はじめの等式から、
6 × (－1) + 8 × 1 = 2 とすぐに右辺が 2 となる等式が得られます。
x = －1, y = 1 と特殊解が得られました。
先ほどの x = 3, y = －2 とは違った特殊解が得られました。
この特殊解は、直線上の具体的な格子点を表すものなので、様々な格子点の座標が存在します。
(－1, 1) + k(4, －3) というベクトル方程式で直線上の格子点 P を表すこともできます。
見た目の式が違っても、直線上のすべての格子点を表すことができているので一般解です。
この例だと、互除法からすぐに特殊解が求まりましたが、計算が大変になることが多いです。
そこで、特殊解を求めるときに、合同式を使って特殊解を求める方法もあります。
※ 合同方程式の解き方という記事で、具体的な求め方について詳しく説明しています。
とにかく、特殊解から直線上の定点さえ求めれば、一次関数の変化の割合からすぐに一般解をパラメータを使って表すことができます。
ここまで、高校の数学で一次不定方程式の様子を見ました。ここから、大学の環論を使って考察をしてみます。
ここからは、整数全体を Z と表すことにします。Z のイデアルの定義です。
【定義】
S ⊂ Z について、次の (1), (2) を満たすものを整数環 Z のイデアルという。
(1) どんな a, b ∈ S に対しても、
a + b ∈ S である。
(2) どんな a ∈ S, z ∈ Z に対しても、
az ∈ Z である。
このイデアルについて、一次不定方程式を考察します。
一次不定方程式 :イデアルを考える
6x + 8y = 2 （x, y は整数）という不定方程式に関連して、次のような整数環 Z の部分集合を考えます。
S = {6x + 8y | x, y ∈ Z} が、その部分集合です。実は、イデアルになっています。
(1) の条件を確認します。
x1, y1, x2, y2 ∈ S とすると、
(6x1 + 8y1) + (6x2 + 8y2)
= 6(x1 + x2) + 8(y1 + y2)
x1 + x2, y1 + y2 は整数なので、
(6x1 + 8y1) + (6x2 + 8y2) ∈ S
次に (2) の条件を確認します。
x, y, z ∈ Z とすると、xz, yz ∈ Z だから、
(6x + 8y)z = 6(xz) + 8(yz) ∈ S
これで、S がイデアルということが確認できました。
ここで、大学で学習する環論の入門的な理論を使います。
ユークリッド整域は単項イデアル整域である。
ユークリッド整域より
整数環 Z は、ユークリッド整域となっています。
そのため、単項イデアル整域なので、Z のどのイデアルも一元生成となっています。
一元生成というのは、ある整数の倍数全体となっているということです。
よって、S = {6x + 8y | x, y ∈ Z} は、たった一つの整数 c の倍数全体となっています。
そのため、S = {cz | z ∈ Z}
{(－c)z | z ∈ Z} = S でもあるので、以下において、c を自然数とします。
※ c = 0 とすると、S = {0} となり、6 ∈ S に反します。
x = 1, y = 0 とすると、
6 ∈ S = {cz | z ∈ Z} ということです。
したがって、6 はある整数 z1 を用いて、
6 = cz1 と表せます。
これは、c が 6 の約数であることを示しています。
今度は、x = 0, y = 1 とすると、
8 ∈ S = {cz | z ∈ Z} となっています。
同様に、c は 8 の約数ということになります。
よって、S を生成していた c は、6 と 8 の公約数ということが分かりました。
実は、さらに踏み込んで、生成元 c が 6 と 8 の最大公約数ということまで断定できます。
生成元を確定させる
今度は、z = 1 として、議論をします。
c = c × 1 ∈ S = {6x + 8y | x, y ∈ Z} となっています。
そのため、ある整数 a, b ∈ Z が存在して、
6a + 8b = c となっています。
ここで、6 と 8 の最大公約数を d とすると、
左辺の 6a + 8b は d で割り切れるので、右辺の c も d で割り切れます。
したがって、生成元 c は d の倍数だということが分かりました。
よって、d ≦ c
一方、c は a と b の公約数だったので、最大公約数 d 以下の値です。
つまり、d ≧ c
以上より、 d = c となり、c が a と b の最大公約数であることが断定できました。
今、6 と 8 と具体的な数字で議論をしましたが、この二つの整数を一般的な整数として文字で置いても、上の議論をそのまま使えます。
整数環 Z がユークリッド整域なので、単項イデアル整域であるということが効いている一次不定方程式の内容でした。
それでは、これで今回のブログ記事を終了します。
読んで頂き、ありがとうございました。