流れる空の中で数学を。

とある数学好きの「手作りすうがく」と「気ままな雑記」。

1変数k次方程式の整数解の絞り込み方

オリジナル数学プログラミング

k次方程式

今日は、次の方程式の整数解を調べます。

$a_k n^k + \cdots +a_0=0$

ここで、上式は次数ｋの整数係数方程式とします。これの自然数解を探すことを考えてみましょう。

一般性を失わずに、全ての係数の最大公約数は１とできます。

定数項

$a_1,\cdots,a_k$ の最大公約数を $g$ とすると、

$gn(\frac{a_k}{g} n^{k-1}+\cdots+\frac{a_1}{g})=-a_0$

となるので、 $g$ が $a_0$ を割り切らなければ、整数解は存在しません。 $g$ が $a_0$ を割り切るならば、整数 $h$ を用いて、 $a_0=gh$ とかけますが、全ての係数の最大公約数は１なので、 $g=1$ となります。

結局、

$n(a_k n^{k-1}+\cdots+a_1)=-a_0$

より、 $n$ は定数項 $a_0$ の正負を含めた約数のいずれかになります。

これで、だいぶ解の候補が絞り込めました。

$m=n\pm 1$ と変数変換してみる

$m=n\pm 1$ とおくと、新しい係数 $b_0,\cdots,b_k$ を用いて、

$b_k m^k+\cdots +b_0=0$

と書き直せます。ここで、

$b_0=a_0\pm a_1 + a_2 \pm \cdots (-1)^k a_k$

となりますが、 $m$ は定数項 $b_0$ の約数となります。

これで、さらに元の方程式の解の候補を絞り込めます。

$m=n\pm l$ と変数変換してみる

同様にして、 $m=n\pm l$ とおくと、新しい係数 $b_0,\cdots,b_k$ を用いて、

$b_k m^k+\cdots +b_0=0$

と書き直せます。ここで、

$b_0=a_0\pm a_1 l + a_2 l^2 \pm \cdots (-l)^k a_k$

となりますが、 $m$ は定数項 $b_0$ の約数となります。

適当な $l$ を選ぶことで、解の候補を絞り込める可能性があります。

不等式

$a_k n^k + \cdots +a_0=0$ を係数が全て正になるように移項して、

$b_l n^l+\cdots=c_m n^m+\cdots$

特に、最も大きな係数や次数を持つ項を $d_j n^j$ とすると、

$b_l n^l+\cdots \gt d_jn^j$

または、

$c_m n^m+\cdots \gt d_jn^j$

等が成り立つので、これから $n$ の範囲を絞り込めます。

例

① $n^2-3n+2=0$

整数解の候補は定数項の約数なので、 $\pm1,\pm2$ となり、これを代入して、 $n=-1,-2$ が解であることがわかります。

② $n^2-3n+5=0$

整数解の候補は定数項の約数なので、 $\pm1,\pm2$ となり、また、 $m=n+1$ の変換を使うと、 $1-3+5=3$ より、可能な候補は $3$ と $5$ の公約数となりますが、これは $n=\pm1$ のみです。これを代入すると、いずれも成り立たないので、整数解はなしです。

③ $2n^5+2n^4-9n^3+4n^2-17n-6=0$

$6$ の約数を代入することで、 $n=-3,2$ が解だとわかります。

④ $n^5+8n^4+n^3-56n^2+58n-60=0$

の定数項は、 $60=2^2\times3\times5$ で約数は12個。

$A \equiv \{\pm1 ,\pm2,\pm3,\pm4,\pm5,\pm6,\pm10,\pm12,\pm15,\pm20,\pm30,\pm60\}$

となる。

移行して、 $n^5+8n^4+n^3+58n=56n^2+60$

となるが、 $n\gt 3$ と仮定すると、

$n^5\lt 56n^2+60\lt 56n^2+63\lt 56n^2+7\times3^2\lt 64n^2$

$n^3\lt 64 \Rightarrow n\lt 4$

よりこれを満たす自然数は存在しないので、矛盾。

従って、正の整数解の候補は $\{1,2\}$ 。実際に代入して、 $n=2$ とわかる。

これより、与式は $n-2$ で割り切れるので、割ると、

$n^4+10n^3+21n^2-14n+30=0$

を得る。 $n=-m$ とおいて、負の整数解を探す。式変形して、

$10m^3=m^4+21m^2+14m+30 \gt m^4$

$10 \gt m \Rightarrow m\le 6$

また、

$10m^3 \gt 21m^2\Rightarrow m\gt 2$

$m \ge 3$

よって、負の整数解の候補は、 $\{-3,-4,-5,-6\}$ である。このとき、 $l$ を整数として、 $m=2l$ とおくと、

$m^4-10m^3+21m^2+14m+30\equiv 30 \not\equiv 0 (\mod 4)$

となり、矛盾。よって、負の整数解の候補は、 $\{-3,-5\}$ である。後は、代入して確かめると、 $n=-5$ のみが負の整数解であることがわかる。

以上をまとめて、求める整数解は、 $n=-5,2$

Pythonのプログラム

gist5635a15b8de6db597b8ae45e72da2cac