370
340 第9章 整数の性質
不定方程式
y
次のような方程式を考えてみます.
-2231x+409y=1
2231x+409y=1 ...... (*)
これを満たす実数x、yの組は無数に存在しま
す.実際,この式を
1
409
この直線上すべての
点(x,y) が解となる
1
2231
1
y=--
x+·
2231
409
409
-x
と変形すると,これはry 平面上の直線となるの
で,この直線上のすべての点(x,y) がこの方程式の解となるわけです.
一般に,文字の数が等号の数より多い方程式は解を定めることができません。
このような方程式のことを不定方程式と呼びます.特に,(*)のようにxy
の一次式で表されるような不定方程式を一次不定方程式と呼びます.
さて,ここで考えたいのは次のことです.
不定方程式
2231x+409y=1 ......(*)
は
りがともに整数であるような解(整数解)を持つだろうか?
これは意外に難しい問題です。 実数の範囲では無数に解を持ったとしても
整数の範囲では解を持つかどうかすらアヤシイのです.
結論から先に言えば
(*)の整数解は存在する
のです.では,それをどうやって示せばいいのでしょう. 妖怪が存在すること
を示す最もストレートな方法は,妖怪を捕まえて連れてくることです. それと
同じで,整数解の存在を示す一番の方法は、 具体的に整数解を作ってみせるこ
とです.ここで役立つのが,先ほど扱ったユークリッドの互除法なのです.
(*)のxyの係数 2231 と 409 に注目し, これをユークリッドの互除法の
要領で「割り算」 していきましょう. すると, 3段階目で余りに1が現れます.
2231=409×5+186 ......①
409=186×2+37
186=37×5+1
1が現れた!
......
2
余りに1が現れたということは, 2つの数の最大公約数は 1 つまり2数は
互いに素であるということです. これはとても重要なポイントなので、頭に入
ておいてください
341
ことは,これらの式を逆にたどるよ
にして1を元の2数を用いて表す」 ことです。 具体的には,次のような作
になります。
⑦→
④→
←
1=186-37 × 5 ③ より
=409×(-5)+186 × 11
186-409-186×2)×5②より37=409-186×2
=409×(-5)+(2231-409×5)×11-0)
=2231×11+409 × (-60) -
186-231-409×5
まず、③により1が 「186と37」 を用いて表され(ア), そこに②を使うと
「409 と 186」 を用いて表され(イ), さらに①を使うと1が 「2231409 」
を用いて表されます(ウ) ウの式は,まさに(*)の整数解 (の1つ)が
であることを教えてくれます。
x=11,y=-60
さて、先ほど注意したように,このようなことができたのは, そもそも
の係数 2231 409 の最大公約数が 1 つまり互いに素であったからです。
つまり、一般に次のことが成り立つことがわかるのです.
不定方程式の整数解
bが互いに素な整数であるとき 1次不定方程式
ax+by=1
は整数解を持つ
ユークリッドの互除法を用いれば, 一次不定方程式の整数解を具体的に作り
出すことができます.ただし,このやり方で見つかる整数解は、あくまで不定
方程式の整数解 「の1つ」であり,それがすべての解であるわけでも、あるい
は最もシンプルな解であるわけでもないことには注意してください。
当然次なる興味は,1次不定方程式の「すべての整数解」を求めることは
きないかということになります.この「すべての整数解」のことを次
定方程式の一般解といいます。その求め方は後ほど詳しく説明しますが、実
「すべての」 整数解を求めるためには, 少なくとも「1つの」 整数解を自
求めなければなりません.そこで,まずは先ほどの作業で「1つの」整数
求める練習をしっかりとしておきましょう。
