2.不定方程式                    戻る

 一般に、未知数と同数の方程式があれば、その方程式を解くことができる。未知数の個
数が方程式の個数より多い場合、その差を自由度といって、解は一意に定まらないことが
多い。

 整数論で話題になるのは、整数係数の方程式が整数解を持つかどうかである。このよう
な問題を、最近は Diophantus の問題といい、その方程式のことを、Diophantus の方
程式
と呼ぶようであるが、当HPでは、高校での学習の延長線ということも考慮に入れて、
旧来の呼び方、不定方程式で通すことにする。

 いくつかのよく知られた定理を確認しておこう。

(1) 1次不定方程式の場合

 ax + by = k が解を持つための必要十分条件は、k が(a,b)で割り切れること

(証明) F = ax + by ( x 、 y は整数)とおく。F の値のうち、最小の正の整数値を、

  d = ax0 + by0 とおく。このとき、ax + by = k は、d の倍数となる。

 実際に、 もしも、 k = md + n (0<n<d)と仮定すると、

  n = k − md = a(x − mx0) + b(y − my0)  これは、d の最小性に矛盾する。

 したがって、特に、a = a・1 + b・0 、b = a・0 + b・1 なので、a、b は、d の倍数。

すなわち、d は、a、b の公約数で、最大公約数 (a,b)の約数となる。

 しかるに、d = ax0 + by0 から、d は、(a,b)の倍数でもあるので、 d = (a,b)

すなわち、  ax0 + by0 = (a,b)  が成り立つ。

 以上から、 ax + by = k が解を持てば、k は、(a,b) で割り切れ、逆に、k が、(a,b)

で割り切れれば、 k=k0(a,b) のとき、 a(k00) + b(k00) = k となり、

ax + by = k は解を持つ。  (証終)

例 2x + 5y = 1 を解け。

 これは、2 と 5 が互いに素で、定理の条件を満たすので解を持つ。私が高校生の頃、上
記の問題を、いつも次のように解いていた。

(解) x = (1 − 5y)/2 = (1 − y)/2 − 2y と変形して、x 、 y が整数であることから、

 1 − y = 2t (t は整数)とおける。 このとき、 x = 5t − 2 、y = −2t + 1  (終)

  (コメント) 最小の係数で割るところがポイントである。

 この解法に似た解法として、オイラーの解法と呼ぶものが存在する。

(別解) 係数の絶対値の最小なものは、2 なので、 5=2・2+1 より、

  2(x + 2y) + y = 1 となる。 x + 2y = t とおくと、 2t + y = 1

 よって、 y = −2t + 1 で、 x = t − 2y = t − 2(−2t + 1) = 5t − 2  (終)

 最近は、次のように解くことが多い。これは、互除法を意識した解法である。(→参考

(別解) 2・(−2) + 5・1 = 1 なので、辺々引いて、 2(x + 2) + 5(y − 1) = 0

   よって、 2(x + 2) = 5(1 − y) で、2 と 5 は互いに素だから、

        x + 2 = 5t 、1 − y = 2t (t は整数)と書ける。

   よって、求める解は、  x = 5t − 2 、y = −2t + 1  (終)

 上記の解法は、不定方程式の特殊解を利用したものである。西武台高校の橋本修司先生
が、不定方程式の特殊解の面白い求め方を紹介されている。

例 29x+13y=1 の特殊解を求めよ。

 いつもだったら適当に、 29×4=116 、13×9=117 などと計算して、

29×(−4)+13×9=1 より、特殊解 x=−4 、y=9 を得るところだが、橋本先生の

方法は、次のようにやるらしい。

 29÷13= ・・・ 3 、13÷3= ・・・ 1  という計算を意識して、 a・m+b・n=1

に対して、 a÷b= ・・・ a−2b 、 b÷(a−2b)= ・・・ −4a+b となる。

 このとき、 m=−4 、n=9 (これは、先の計算結果と一致する!)

例 17x−24y=2 の特殊解を求めよ。

 まず、17x−24y=2 の特殊解を求める。

 −24÷17=−2 ・・・ 10 、 17÷10= ・・・ 7 、10÷7= ・・・ 3

 7÷3= ・・・ 1  という計算を意識して、 a・m+b・n=1

に対して、 b÷a=−2 ・・・ 2a+b 、 a÷(2a+b)= ・・・ −a−b 、

 (2a+b)÷(−a−b)= ・・・ 3a+2b 、

 (−a−b)÷(3a+2b)= ・・・ −7−5b となる。

 このとき、 m=−7 、n=−5

 したがって、 17x−24y=2 の特殊解は、 x=−14 、 y=−10


(コメント) 橋本先生の方法は、ほぼ機械的にできるという利点はあるのだが、正直に言っ
      て少し面倒くさい。

  17x−24y=2 の特殊解は、やはり、 17×7−24×5=−1 から、x=−14 、
y=−10 と軽妙に答えたいところだ。


(追記) 平成26年4月27日付け

 29と13は互いに素なので、29x+13y=1 となる整数 x、y が存在することは知られて
いるわけであるが、不定方程式 29x+13y=1 を解く場合、特殊解 x0、y0 (すなわち、
29x0+13y0=1 )を見つけることが一つの解法のアプローチとなる。

 そのための方策として、上記では、西武台高校の橋本修司先生の方法を紹介したわけで
あるが、次のような方法もあることを最近知ることができた。

(参考文献: 臼井達哉 著 「互除法の逆行の記法の改良」 (数研通信 No.79))

 互除法を意識すれば、 29÷13=2 ・・・ 3 、 13÷3=4 ・・・ 1 より、29と13は

互いに素であることが分かる。問題は、不定方程式 29x+13y=1 を解く場合、特殊解 x0

0 を見いだすことである。互除法の書かれた書籍によれば通常次のようにして求められる。

 13=3×4+1 に、29=13×2+3 を変形した 3=29−13×2 を代入して、

  13=(29−13×2)×4+1 より、 29×(−4)+13×9=1

 よって、求める特殊解 x0、y0 は、x0=−4 、y0=9 となる。

 互除法で得られた式を活用して、上記の計算を精査すれば、新しい視点での計算が可能
となる。

 不定方程式 29x+13y=1 において、29=13×+3 から、

   (13×2+3)x+13y=1 すなわち、 13(2x+y)+3x=1

 ここで、2x+y=z とおくと、 13z+3x=1

 さらに、13=3×+1 から、 (3×4+1)z+3x=1 すなわち、 3(4z+x)+z=1

 ここで、4z+x=w とおくと、 3w+z=1 となる。

 この不定方程式の特殊解として、 w=0 、z=1 がとれることは明らか。

 このとき、 x=w−4z=0+(−4)・1=−4

        y=z−2x=1+(−2)(−4)=9

と、元の不定方程式の特殊解が求められる。

 上記の計算を筆算形式で表せば、この解法の簡便さが組立除法のような感覚で理解でき
ると思う。

     

 読者の方のために練習問題を残しておこう。

練習問題  不定方程式 47x+13y=1 の特殊解を一つ見つけよ。

(解)
        よって、特殊解として、 x=5 、y=−18


(追記) 平成27年6月7日付け

 上記の練習問題で、特殊解を求める場合に次のような方法があることを最近知ることが
出来た。

 47x+13y=8x+13(3x+y)=1 で、 8×5+13×(−3)=1 から、

 x=5 で、 3x+y=−3 から、 y=−3x−3=−18

 このような ax+by=c 型の不定方程式の問題は最近大学入試で目立ってきている。

(1) 鹿児島大学 37x+32y=1

(2) 上智大学 41x+355y=1

(3) 名城大学 71x−33y=1

 不定方程式は、その特殊解が求まれば一般解は容易に求められる。特殊解の計算には
ユークリッドの互除法が正統的な方法であるが、計算が煩雑で計算ミスも起こりやすい。

 特殊解は軽妙に暗算で求められれば最高であるが、上記のような解法を援用すれば多少
は負担軽減となることだろう。

 (1)(2)(3)の特殊解を求めてみよう。

(1) 5x+32(x+y)=1 より、 5(7x+6y)+2(x+y)=1

    7x+6y=1 、 x+y=−2 より、 x=1+12=13 、y=−15

(2) 41(x+8y)+27y=27(x+9y)+14(x+8y)=1 において、

   x+9y=−1 、 x+8y=2 より、 y=−1−2=−3 、x=26

(別解) 41(x+9y)−14y=1 より、x+9y=−1、y=−3 から、x=26 としてもよい。

(3) 5x+33(2x−y)=5(13x−6y)+3(2x−y)=1 において、

   13x−6y=−1 、2x−y=2 より、 x=−1−2×6=−13、 y=−28


 上記の定理は、2元の不定方程式に関するものだったが、同様の推論により、3元以上
の1次不定方程式においても同様の結果が得られる。

例 7x + 4y − 8z =23 の一般解を求めよ。

(解) 7、4、8 は互いに素なので、解は存在する。

 7 = 2・4 − 1 、8 = 2・4 なので、 4(2x + y −2z) − x = 23

 2x + y −2z = u とおくと、 4u − x = 23 より、 x = 4u − 23

 このとき、 y = −2x + 2z + u = −7u + 2z + 46

 ここで、 u = s + 6 、 z = t とおくと、求める解は、

   x = 4s + 1 、 y = −7s + 2t + 4 (s、t は整数)  (終)

 このように、1次の不定方程式は、その解法が確立されているので、話題の中心を高次
の不定方程式に移そう。

 2元2次の不定方程式としては、ペル方程式が有名である。これについては、当HPで既
に言及しているところである。(→参考:ペル方程式

 ペル方程式に劣らず有用で、中学校で学習する三平方の定理も見方を変えれば不定方
程式である。

例 不定方程式 2+y2=z2 の正の整数解は、ピュタゴラス数といわれる。(→参考

 平成7年(1995年) アンドリュー・ワイルズにより

方程式 X+Y=Z (n は3以上の自然数)を満たす自然数解(X,Y,Z)はない 

ということが証明された。

(証明の雰囲気としては、解が存在するとすると、ある種の楕円曲線が存在することにな
るが、その楕円曲線は奇妙な性質を有していて、そのような楕円曲線は存在し得ないこ
とが分かっているから矛盾という風にやるらしい。)

 一般の場合の証明は、ワイルズさんに聞くとして、n=4 の場合に解がないことは以前
からよく知られている事実である。

 オイラーによって示された証明を下記でなぞってみよう。

(証明) いま、 x4 + y4 = z4 の正の整数解が存在すると仮定する。

このとき、 z2 = u とおくと、 x4 + y4 = u2 にも正の整数解が存在する。

正の整数解のうち、u の値が最小のものを、 (x1、y1、u1) とおく。

u の値の最小性から、 x1、y1、u1 は互いに素としてよい。

 よって、 x12、y12、u1 も互いに素で、x12、y12、u1 は、ピュタゴラス数である。

このとき、 x12=m2−n2 、y12=2mn 、u1=m2+n2 となる正の整数が存在する。

ただし、m、n は互いに素で、mは奇数で、nは偶数である。

 (ここで、もしも mは偶数で、nは奇数とすると、 x12≡−1 (mod 4) となるが、これは起こり得ない。

 このことから、 y12=2mn より、 m=u22 、 2n=4v2 となる正の整数 u 、v が存

在する。

 ところで、 x12+n2=m2 において、x1、n、m も互いに素であるので、同様にして、

    x1=m12−n12 、n=2m11 、m=m12+n12 となる正の整数が存在する。

  ただし、m1、n1 は互いに素で、一方は奇数で、他方は偶数である。

2n=4v2 を n=2m11 に代入して、 v2=m11

 このことから、 m1=x22 、 n1=y22 と書ける。

したがって、 m=u22 と、これらを m=m12+n12 に代入して、 x24+y24=u22

が成り立つ。

 よって、 (x2、y2、u2)は、x4 + y4 = u2 の解になる。

u の最小性から、 u1≦u2 でなければならないが、u1=m2+n2 、 m=u22 により、

2≦m<u1 となり、これは矛盾である。

 したがって、所要の正の整数解は存在しない。(証終)


(追記) S(H)さんからの出題です。(平成25年9月16日付け)

 7x8−19xyz+5y8+3z8=0 の整数解を求めよ。



  以下、工事中