けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

もこもこさんの整数方程式 x^2 + 3x = y^2

もこもこさんが Twitter で挙げてた問題に色んな解法を寄せられていて面白かったのでメモします。

問題


 x^{2} + 3x = y^{2} を満たす整数  (x, y) をすべて求めよ


   

解法 1: 判別式が平方数 (Pulmn さんの解法)

恐らく受験数学的には最もメジャーな解法です。

 x^{2} + 3x - y^{2} = 0二次方程式として見たときに、 x について解いてみると

 x = \frac{-3 ± \sqrt{9 + 4y^{2}}}{2}

となります。 9 + 4y^{2} \ge 9 >  0 が常に成り立つので、 y の値がどのような値であっても  x は実数解を 2 個もつことになります。そしてその実数解が整数でなければなりません。そのためには

  •  9 + 4y^{2} が平方数であることが必要

ということになります。したがって、整数  n を用いて

 9 + 4y^{2} = n^{2}

と表せます。式変形して、

 (n + 2y)(n - 2y) = 9

となります。 n+2y, n-2y は整数なのでありうる組み合わせは

 (n + 2y, n - 2y) = (1, 9), (3, 3), (9, 1), (-1, -9), (-3, -3), (-9, -1)

となるのでそれぞれ  (y, n) について解くと

 (y, n) = (-2, 5), (0, 3), (2, 5), (2, -5), (0, -3), (-2, -5)

となります。つまり、 y としてありうるものは

 y = 0, ±2

に絞られました。これらに対して実際に  x の値も求めてみると

  •  y = 0 のとき、 x = 0, -3
  •  y = 2 のとき、 x = 1, -4
  •  y = -2 のとき、 x = 1, -4

となります。これらの  x はすべて整数になっているので、求める整数解は

 (x, y) = (0, 0), (-3, 0), (1, ±2), (-4, ±2)

となります。

解法 2: 頑張って因数分解する解法 (tempura さんの解法)

ひたすら式変形して行きます。式変形がカッコイイです。

 x^{2} + 3x = y^{2}
 (x + \frac{3}{2})^{2} - \frac{9}{4} = y^{2} (左辺を平方完成します)
 (2x + 3)^{2} - 9 = 4y^{2} (両辺を 4 倍します)
 (2x + 3)^{2} - 4y^{2} = 9 (因数分解する形に持ち込みます)
 (2x + 2y + 3)(2x - 2y + 3) = 9

 2x + 2y + 3, 2x - 2y + 3 は整数なのでありうる組み合わせは

 (2x + 2y + 3, 2x - 2y + 3) = (1, 9), (3, 3), (9, 1), (-1, -9), (-3, -3), (-9, -1)

に絞られます。それぞれ解くことで、

 (x, y) = (1, -2), (0, 0), (1, 2), (-4, 2), (-3, 0), (-4, -2)

となります。

コメント

式変形のモチベーションとしては、

  • もし  x^{2} + 3x = y^{2} 3x の部分がなかったら「平方の差」による因数分解の形に持ち込めそう
  • → それなら左辺を平方完成すればよい
  • → 分数が出て来てしまったので両辺 4 倍すれば整数になる
  • → 無事に「平方の差」の形になったので因数分解できた

という感じです。

解法 3: 「互いに素」の性質を利用する解法 (僕の解法)

有名な東大入試問題 (a2 - a が 10000 の倍数となる奇数 a を求める問題) を知っているとピンと来る解法かと思います。少し理解が難しいかもしれません。

 x^{2} + 3x = y^{2}
 x(x + 3) = y^{2}

となる。ここで、ユークリッドの互除法により、

 {\rm GCD}(x, x + 3) = {\rm GCD}(x, 3) = 1 または 3

となることに注目します。つまり、 x x + 3 との最大公約数は、 1 3 以外にはありえないということです。最後の「 {\rm GCD}(x, 3) = 1 または 3」のところは、 3 の正の約数が  1 3 しかないことに依っています。ここから場合分けします。

GCD(x, x + 3) = 1 のとき

一般に「互いに素な 2 つの整数  a, b の積  ab が平方数になるならば、 a b も平方数 (かそれにマイナスをつけたもの)」になります。これは素因数分解を考えてみるとわかります。受験数学においても最難関問題ではよく見かけるテクニックです。このことを用いると整数  m, n を用いて

  •  x = ±m^{2}
  •  x + 3 = ±n^{2}

と表せることになります (複合同順)。よって

 n^{2} - m^{2} = ±3

ということになり、「差が 3 になる平方数の組」は 1 と 4 しかないことから

  •  x = 1 (このとき  x + 3 = 4)
  •  x = -4 (このとき  x + 3 = -1)

のみに絞られます。 x = 1 となる  y を具体的に求めると  y = ±2 となり、 x = -4 となる  y も同じく  y = ±2 となります。

GCD(x, x + 3) = 3 のとき

先ほどの拡張で、

「最大公約数が  d となっている 2 つの整数  a, b の積  ab が平方数ならば、整数  m, n を用いて  a = ±dm^{2},  b = ±dn^{2} (複合同順) と表せる」

ということが言えます。これもよく見るテクニックです。念のために証明してみます。 a b の最大公約数が  d のとき、互いに素な整数  a', b' を用いて

  •  a = da'
  •  b = db'

と表せます。 ab が平方数であることから  d^{2}a'b' が平方数ということになり、したがって  a'b' も平方数です。 a' b' は互いに素であったので、 a' = ±m^{2},  b' = ±n^{2} (複合同順) とおくことができて定理が従います。

さて、元の問題に戻ると

  •  x = ±3m^{2}
  •  x + 3 = ±3n^{2}

とおけることになります (複合同順)。よって

 n^{2} - m^{2} = ±1

ということになり、「差が 1 になる平方数の組」は 0 と 1 しかないことから

  •  x = 0 (このとき  x + 3 = 3)
  •  x = -3 (このとき  x + 3 = 0)

のみに絞られます。 x = 0 となる  y を具体的に求めると  y = 0 となり、 x = -3 となる  y y = 0 となります。

以上をまとめて、求める整数解は

 (x, y) = (1, ±2), (-4, ±2), (0, 0), (-3, 0)

となります。

解法 4: 平方数がまばらであることを利用 (kaito さんの解法)

数学オリンピックでは超頻出のテクニックですが、受験数学でも最難関問題で時々見かけることがあります。平方数がまばらであることを利用します。

本問題はいわば「 x^{2} + 3x が平方数となるような  x を求めよ」ということでもあります。ここで着想としては、 x^{2} + 3x というのは、一般的な  x に対しては

  •  (x + 1)^{2} = x^{2} + 2x + 1
  •  (x + 2)^{2} = x^{2} + 4x + 4

の間に入ってしまいそう...というのがあります ( 3x 2x 4x の間になるため)。しかし、「間に入る」というのはあってはならないことなのです。なぜなら、 x^{2} + 3x は平方数でなければなりませんが、 (x + 1)^{2} (x + 2)^{2} は連続する平方数のためこの隙間に平方数はありません。つまり、

 x^{2} + 3x (x + 1)^{2} (x + 2)^{2} との隙間に挟まれてしまうとき、 x^{2} + 3x は平方数とはならない」

ということになります。このことを活用して  x を絞り込みます。

  •  (x + 1)^{2} <  x^{2} + 3x <  (x + 2)^{2}

を解くと  x >  1 となります。つまり、 x >  1 のときには「解なし」です。次に

  •  (x + 2)^{2} <  x^{2} + 3x <  (x + 1)^{2}

を解くと  x <  -4 となります。つまり、 x <  -4 のときには「解なし」です。

以上をまとめると、 x^{2} + 3x が平方数となりうる  x の範囲は

  •  -4 \le x \le 1

に絞られました。あとはしらみつぶしに調べることで、整数解

 (x, y) = (-4, ±2), (-3, 0), (0, 0), (1, ±2)

が得られます。

おわりに

整数方程式に挑む方法はこのページに示されている通り、

と様々な方法がありますが、この記事の問題は、これらの方法をいろいろ学べて面白いと思いました。