ブログ「サイバー少年」

ブログ「サイバー少年」へようこそ!
小学六年生ごろからプログラミングを趣味にしている高校生のブログです。
勉強したことについての記事などを書いています。フリーソフトも制作、公開しています。
(当ブログについて詳しくは「ブログ概要紹介」を参照)

サイバー少年が作ったフリーソフトは「サイバー少年の作品展示場」へ

一次不定方程式について調べた

前々回の記事「[環論] 素元と既約元の違いってなんなのよ」および、前回記事「数学ネタは人気が出ないのか…」で書いたとおり、
群・環・体の本を読んでいたら不定方程式にぶち当たったので、最近は群・環・体をやらずに不定方程式について調べていました。

群・環・体の本にも予備知識として不定方程式について解説があったので、それを読んだのと、あと不定方程式は高校一年生のときにやりましたから、数Aの教科書をひっぱりだしてきて読んでみました。

覚えてないからな!!

そこで思ったのですが、本によって不定方程式の解法にしても全然、やり方が違いますね。
数学って知識を丸コピするよりか、自分で考える学問ですから考える人が違うと内容もだいぶ違ってしまうんでしょうね。

私は丸コピしか出来ないですが…。


さて、今回はレポートを書く気分で、(一次の)不定方程式について調べて学んだことを記していきたいと思います。




最初に、高校の数Aの教科書に書いてあった解法を紹介しますが、
40x + 21y = 4
みたいな不定方程式があたえられたときに、

「まず解を一組だけ見つけてくれよな!!」という話になります。

いや、その解の見つけ方を教えろやと言いたくなるのですが、それにはユークリッドの互除法を使えます。

しかし、右辺の= 4のところは40と21の最大公約数になってないといけないのですが、最大公約数の1になっていないので、このままでは出来ません。
そこで、なんとも強引に見えますが40x + 21y = 1にしてしまいます。

この40x + 21y = 1の解を見つけたあと解を4倍にすれば、40x + 21yが4倍になるので、40x + 21y = 4のほうの解になりますね。


さて、ユークリッドの互除法を適用してみます。
40 = 21×1 + 19
21 = 19×1 + 2
19 = 2×9 + 1
2 = 1×2 + 0

最後の等式はいいとして、他の等式をそれぞれ変形します。
19 = 40 - 21×1
2 = 21 - 19×1
1 = 19 - 2×9

すると
1 = 19 - 2×9 = (40 - 21) - (21 - 19)×9
= (40 - 21) - (21×9 - 19×9)
= (40 - 21) - (21×9 - (40 - 21)×9)
= (40 - 21) - (21×9 - (40×9 - 21×9))
= 40 - 21 - 21×9 + 40×9 - 21×9
= 40×10 + 21×(-19)

という感じで、等式による置き換えを帰納的に適用していって最終的に40と21の倍数だけを項にできます。

これは元をたどれば1と等しかったので、
1 = 40×10 + 21×(-19)

つまりx = 10, y = -19として、
40x + 21y = 1が成り立つことがわかります。

そして、この解を4倍することになっていたので、x = 40, y  -76が、
40x + 21y = 4の解となります。


次に、他の解はどうなるのかという話ですが、xが増えると40xという項が大きくなります。
そのとき等式を満たしたいならどうするかというと、40xという項が増えた分だけ21yという項を減らさないといけないですね。

xがa増えてyがb減るなら、40xの増えた分は40a、21yの減った分は21bと、整数a,bを用いて置けますが、
40a = 21bでないといけないわけです。

40aは40の倍数で、21bは21の倍数ですから、両方の倍数となる数を作らないといけないので、aおよびbをなんとかして40と21の公倍数を作らなければなりません。

よって、とりあえず最小公倍数を作るとすると、40と21は互いに素なのでお互いの数がまるごと入ってa = 21, b = 40となります。

最小でない他の公倍数も、考えてみれば最小公倍数の倍数なので、整数sを用いてa = 21s, b = 40sと置けばいいですね。

これが成り立たなければならないので、
x = 40 + 21s, y = -76 - 40s
もしくは増えるほうと減るほうを逆にして
x = 40 - 21s, y = -76 + 40s
が一般解となります。(同じ解です。)

他の不定方程式でも仕組みは同じなので、同じようにユークリッドの互除法から最小公倍数までの手順で一般解が出ます。

不定方程式の右辺が、xとyの係数の最大公約数の倍数になっていれば。

なお、さもなければxとyの係数の最大公約数を右辺とする不定方程式の解は出ますが、その解を整数倍してもともとの不定方程式の解を出すことができないので、少なくともこの解法では解けません。




続いて、群・環・体の本に書いてあった解法を紹介します。

まず、ax + by = cについて、解が存在するならcはaとbの最大公約数の倍数となるはずです。

なぜなら特定の整数xとyについてax + by = cが成り立つわけで、
左辺を最大公約数nでくくるとn(a'x + b'y) = cと表せますから、(a'x + b'y)は整数なのでcはnの倍数です。

この命題の対偶をとって、cがaとbの最大公約数の倍数とならなければ解は存在しません。
諦めましょう。

cがaとbの最大公約数の倍数であるならば、不定方程式の全体をその最大公約数で割ってもいいですね。
解は同じです。

このとき、aとbは互いに素になります。

では、すでに互いに素である先ほどの例を持ってきますが、
40x + 21y = 4を解いてみましょう。

小さいほうの係数で左辺をくくって、大きいほうの係数が余りますから、それは括弧の外に出します。

19x + 21(x + y) = 4
この(x + y)を、s = x + yと置くと、
19x + 21s = 4です。

もう一回やります。
19(x + s) + 2s = 4
この(x + s)を、t = x + sと置くと、
19t + 2s = 4です。

さらに
t + 2(9t + s) = 4
この(9t + s)をu = 9t + sとして、
t + 2u = 4です。

ここで
t = 4 - 2uと変形できるようになりました。

このuに好きな整数を入れていいことにします。
すると、整数tが決まりますね。

u = 9t + sだったので、変形してs = u - 9t = u - 9(4 - 2u) = 19u - 36です。
t = x + sだったので、変形してx = t - s = 4 - 2u - (19u - 36) = -21u + 40。
s = x + yだったので、変形してy = s - x = 19u - 36 - (-21u + 40) = 40u - 76となります。

つまりuに好きな整数を入れれば全ての変数が決まってしまうわけです。


実は先ほどの
40x + 21y = 4
19x + 21s = 4
19t + 2s = 4
t + 2u = 4
というふうに変数を置きかえていくとき、変数の係数が(小さい数で大きい数を割り始めた場合の)ユークリッドの互除法の経過と一致します。

順番が違う箇所がありますが、割る数に相当する数が余りに相当する数より常に大きいはずなので、並び替えれば分かります。
なぜユークリッドの互除法の経過と一致するのかというと、小さい係数が大きい係数を割ることにして、割る数と余りを次の係数にしていくからですね。

ということは、40と21が互いに素、つまり最大公約数が1であるなら、最終的に係数が1(もしくは-1)になる変数が出てきます。

その変数について変形して、もうひとつの変数に好きな変数値を入れていいことにすれば、整数の項しか発生しないので、その変数は整数として決まります。

これで、一番最後の等式に出てくる変数は、片方を決めれば両方が既知となることをお分かりいただけたと思います。


次に、なぜ他の変数も既知となるのかの証明ですが、そもそも既存の等式から新しい変数を用いた等式を作成するのがどのような仕組みになっているのかというと、

ax + by = c (|a| > |b|)を
rx + b(nx + y) = c (a = nb + r, 1 <= r < |b|)とくくって、
a'x + by' = c (a' = r, y' = nx + y)

という等式を作成していることになります。
あとは厳密にやるなら数学的帰納法になりますね。

既存の等式から新しい変数を用いた等式を作成することを式の変換を適用すると呼ぶことにして、

最初の等式(不定方程式)に、n回、式の変換を適用したときの式に現れる変数がすべて既知なら、適用前、つまりn-1回、式の変換を適用したときの式に現れる変数も既知であることを証明します。

x,yをn-1回目の変数、x,y'をn回目の変数だとして、
x = x
y = y' - nx

と表せるため(変数以外の数は既知です。)、n-1回目の式の変数も既知であることが証明されました。

続いて、n回、式の変換を適用したときの式に現れる変数が既知であるようなnが存在することを証明します。

これは前述のとおり最初の不定方程式のふたつの係数の最大公約数が1であるなら、最終的に係数が1(もしくは-1)となる変数が現れてそれについて解けば、もうひとつの変数を好きに決めることで、どちらも既知となるので、そのとき条件を満たします。

これより特定のn回以下の式の変換を適用したときの式に現れる変数はすべて既知であることが証明されたので、0回目においてもx,yは既知であります。



というわけで、最後の証明なんかは実は記載されていなかったので自分でなぜこうなるんだろうと考えて作成しました。

まあ、ひとつずつ変換を適用していくという構造に気づくのと、数学的帰納法の知識があれば簡単に分かってしまうレベルではありますね。

ただ、今ちょっと思ったのですが、上の例でいえばuに好きな整数を入れていけばそれぞれx,yが定まるというのは言えてるわけですけども、uに好きな整数を入れて作った解がこの不定方程式の解の全てであるということが言えていない気がしますね…。

それについての証明も加えないと駄目なんじゃないかと思いましたが、余力がありません。

誰かご指導ください。(切実)


いや~、ただ、それなりに不定方程式について理解できたので良かったですね。

ちなみに前回記事「
数学ネタは人気が出ないのか…」で取り上げた、
「0 <= x < pとなる解を持つか問題」(詳しくは記事を読んでね)ですが、

これも、本記事の前半で扱ったとおり、a < pでpとaが互いに素になるわけですから、x = ps + ○になるわけなので、直感的に適当にsを決めれば0 <= x < pに収まるなと分かりますよね。

厳密な証明は分かりませんでしたが、不等式を使うのかな。


それでは、次回からは群・環・体の勉強を再開したいと思います。

tag: 数学 方程式 勉強 素数 証明 数学的帰納法 学校

コメント

コメントの投稿

トラックバック

トラックバック URL
http://cyberboy6.blog.fc2.com/tb.php/502-31ae2765
この記事にトラックバックする(FC2ブログユーザー)

当ブログをご利用(閲覧等)になる場合は必ず「当ブログの利用規定」をお守りください。