2014/05/05

不定方程式の解き方6パターン

分野: まとめ

方程式の数よりも変数の数の方が多い方程式系のことを不定方程式といいます。

特に,整数係数の不定方程式をディオファントス方程式といいます。
ディオファントス方程式の整数解を求める問題は入試や数学オリンピックで超頻出なので主要な6パターンを整理しておきます。

1:二変数一次不定方程式

大学入試で頻出の $ax+by=c$ 型は機械的に解くことができます。
→一次不定方程式ax+by=cの整数解

2:平方剰余,立方剰余

平方数や立方数は剰余に制約がつきます。→平方剰余と基本的な問題

$x^2$ は $3$ で割った余りが $0$ か $1$ なので,$x^2+1=3y$ は整数解を持たない。

上記の例のように整数解を持たないことがいきなり示せるのは稀ですが,例えば「 $x$ は $3$ の倍数になる」など解の範囲が絞れる場合があります。困ったらとりあえず $3,4,5,7$ で割った余りを考えて解を絞れないか検討してみましょう。

3:因数分解

$xy+ax+by+c=0$ 型は$(x+b)(y+a)=ab-c$ と因数分解することができます。 $x+b,y+a$ がそれぞれ $ab-c$ の約数になることから解の候補が絞られます。

上記の例以外にも,$a^n-b^n,a^n+b^n,a^4+4b^4$ の形を作り出せたら因数分解してみましょう。
→因数分解公式(n乗の差、和)
→因数分解公式(ソフィージェルマンの恒等式)

4:不等式で範囲を絞る

対称な不定方程式は変数の間に大小関係を決めても一般性を失わないので不等式でおさえる手法が使いやすいです。

$\dfrac{1}{x}+\dfrac{1}{y}=1$
$x\geq y$ としても一般性を失わない。左辺 $\leq \dfrac{2}{y}$ より $y\geq 3$ だとおかしい。よって解の候補が絞れる。

5;一般の二次不定方程式なら判別式

$ax^2+bxy+cy^2+dx+ey+f=0$ 型は $x$ または $y$ についての2次方程式と見た時に判別式が平方数になるという条件から解の候補が絞れます。 $x$ についてうまくいかなくても $y$ についてだとうまくいくという場合もあります。

判別式でうまくいかないときはペル方程式に帰着することが多いです。→ペル方程式に関する基本的な性質まとめ

6:無限降下法

数学オリンピックの難問に多いタイプです。
例えば,フェルマーの最終定理の $n=4$ の場合の証明は無限降下法を使うとうまくいきます。(→無限降下法の整数問題への応用例の下の方)

無限降下法に似たタイプ「最小性に矛盾させる」方法としてVieta jumpingというものもあります。
数オリのテクニック〜Vieta jumping〜

難しい問題はこれらのテクニックをうまく組み合わせて解く必要があります。例えば2と3を併用するとピタゴラス数を求めることができます。→ピタゴラス数の求め方とその証明

あとは,数オリではフェルマーの小定理もたまに使います。
→フェルマーの小定理の証明と例題

とにかくいろいろな問題を解いて各パターンに慣れるべし
分野: まとめ