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 の整数解を求めよ。


(追記) 令和4年1月18日付け

 上記のオイラーの解法を用いる不定方程式の問題が、令和4年度の大学入学共通テスト
(数学I・A)で出題された。新聞の問題解説でも紹介された、今年度を代表する新傾向の問
題と言える。誘導付きがこれまでのセンター試験の王道であったが、最後の設問では、誘
導なしで解答を作ってねと示唆される、2次試験数学レベルの対応が必要な問題となって
いる。受験生、特に文系の受験生泣かせの問題ですね!

第4問(問題文を一部改題)
(1) 54=625を24=16で割ったときの余りは、1に等しい。このことを用いると、不定方
  程式 54x−24y=1 ・・・ (イ) の整数解のうち、x が正の整数で最小になるときの
  x、y の値を求めよ。

  また、(イ)の整数解のうち、x が2桁の正の整数で最小となるときの x、y の値を求めよ。

(2) 次に、6252を55で割ったときの余りと、25で割ったときの余りについて考える。

  まず、6252=58 であり、m=39とするとき、6252 をmの2次式で表せ。

  これらより、6252 を55で割ったときの余りと、25で割ったときの余りが分かる。

(3) (2)の考察は、不定方程式 55x−25y=1 ・・・ (ロ) の整数解を調べるために利
  用できる。

 x、y を(ロ)の整数解とする。55x は55の倍数であり、25で割ったときの余りは1となる。

 よって、(2)により、55x−6252は55でも25でも割り切れる。55と25は互いに素なので、
5x−6252は55・25の倍数である。

 このことから、(ロ)の整数解のうち、x が3桁の正の整数で最小となるときの x、y の値を
求めよ。

(4) 114を24で割ったときの余りは1に等しい。不定方程式 115x−25y=1の整数解の
  うち、x が正の整数で最小となるときの x、y の値を求めよ。

(解)(1) 54=625=24・39+1 より、 (24・39+1)x−24y=1

 すなわち、 x=24(y−39x)+1 で、 y−39x=z とおくと、zは整数で、 x=24z+1

 x は、「正の整数で最小」なので、z=0 と定まり、このとき、x=1で、y=39

 x は、「2桁の正の整数で最小」なので、z=1 と定まり、このとき、x=17で、y=664

(2) 625=24・m+1 より、 6252=(24・m+1)2=28・m2+25・m+1

  このとき、6252を55で割ったときの余りは0で、25で割ったときの余りは1である。

(3) 55x=25y+1 から、55xを25で割った余りは1なので、55x−6252は55でも25
  でも割り切れる。

  55と25は互いに素なので、55x−6252は、55・25の倍数である。

  すなわち、 55x−6252=55・25z (zは整数) から、 x=125+25

 x は、「3桁の正の整数で最小」なので、z=0 と定まり、このとき、x=125で、

 25y=55x−1=58−1=(54+1)(54−1)
                =626・624=(2・313)(24・39)=25・12207

 から、 y=12207

(4) 112≡9 (mod 24) より、 114≡81≡1 (mod 24

 すなわち、 114=24k+1 (kは整数) から、 118=282+25k+1 なので、

 118≡1 (mod 25) である。

 また、115x−25y=1の整数解 x、y について、115x≡1 (mod 25) である。

 そこで、 115x−118≡0 (mod 115) かつ、 115x−118≡0 (mod 25

さらに、115と25は互いに素なので、 115x−118≡0 (mod 115・25

 以上から、 115x−118=115・25・z (zは整数)

 すなわち、 x=25・z+113 と書ける。

 x は、「正の整数で最小」なので、z=−41 と定まり、このとき、x=19 である。

 このとき、 25y=115・19−1=3059968 より、 y=95624  (終)


((4)の別解)・・・マークシート方式なので、設問の誘導に従うのが王道ですが、直接的に
          求めた方が速い場合も多い。

 115x−25y=1 を mod 25=32 で考えると、 115x≡1

 112=121≡−7 なので、 115≡(−7)2・11=−5 より、 −5x≡1

 27x≡1 とも書けるので、結局は、 2x≡6 となる。 よって、 x≡19

 したがって、求める「正の整数で最小」な x の値は、 x=19 となる。

 このとき、 25y=115・19−1=3059968 より、 y=95624  (別解終)


(コメント) こんなに計算が煩雑なのに、配点が20点というのは割りにあわないですね!


 ks さんからのコメントです。(令和4年11月12日付け)

 整数解を求める一次不定方程式について、

 「ax+by=c が解を持つ ⇔ cが、a、b の公約数で割れる」

 未知数が、三つ以上でも、言えますか?必要性は、分かりますが...。ご教授ください。


(コメント) 高木貞治 著「初等整数論講義」によれば、

 「ax+by+cz=k が解を持つ ⇔ k が、d=(a,b,c) で割り切れる」

が成り立ち、変数の数は任意とのことです。


 らすかるさんからのコメントです。(令和4年11月12日付け)

 ax+by+cz=d において、d が a、b、c の最大公約数で割り切れないときは明らかに解を
持ちません。(左辺は、a、b、c の最大公約数の倍数にしかならないため)

 d が a、b、c の最大公約数で割り切れる場合は、最大公約数で割ったものを、あらためて
a、b、c、d とすれば、

 ax+by+cz=d  (a,b,c)=1

です。このとき、

 b=Bg 、c=Cg 、(B,C)=1 とすれば、 (a,b,c)=1 から (a,g)=1 であり、

 ax+Bgy+Cgz=d すなわち、 ax+g(By+Cz)=d

 これは、By+Cz=w とおけば、 ax+gw=d 、(a,g)=1 なので、解を持ちます。

 この解のwに対して、 By+Cz=w は、(B,C)=1 から解を持ちますので、元の式も解
を持つことになります。



  以下、工事中