2014/04/13

無限降下法の整数問題への応用例

分野: 整数問題  レベル: 数学オリンピック

無限降下法(後ろ向き帰納法)と呼ばれる証明方法を紹介します。無限降下法の簡単な応用例として $\sqrt{3}$ が無理数であることの証明を紹介し,発展的な応用例としてフェルマーの最終定理の $n=4$ の場合の証明を行います。

無限降下法

無限降下法は数学オリンピックの整数問題でしばしば必要になります。入試問題でもまれに出題されます。また,大学の数学では数論{整数問題)以外の分野でも多用される重要な考え方です。

無限降下法とは,仮定を満たす「より小さいもの」を作り出すことで矛盾を示す背理法の一種です。

無限降下法は以下のどちらかの流れで整数問題の難問の証明中にさらっと用いられます。

1:〜を満たす最小のものを $k$ とおくとより小さいもので〜を満たすものが構成できるので矛盾
2:〜を満たすものがあるとより小さいもので〜を満たすものが構成できて,いくらでも繰り返すことができるので矛盾

本質的に上記2つの説明は同じことですが解答作成者の気分次第でどちらの書き方も使われています。これらの文言を見たら無限降下法を連想しましょう。

無理数であることの証明

無限降下法を用いた証明の例として,$\sqrt{3}$ が無理数であることを証明します。

証明

$\sqrt{3}$ が有理数であると仮定すると,
$\sqrt{3}=\dfrac{n}{m}\:,m, n$ は自然数とおける。
$3m^2=n^2$ となるので $n$ は $3$ の倍数であることが分かり $n=3n’$とおける。
すると,$m^2=3n’^2$ となり,$m$ も $3$ の倍数であることが分かり $m=3m’$とおける。
もとの方程式に代入すると $3m’^2=n’^2$ となる。
よって,自然数 $m,n$ が方程式 $3m^2=n^2$ を満たすなら $\dfrac{m}{3},\dfrac{n}{3}$ もそれぞれ自然数で同じ方程式を満たす。この議論を繰り返していくと $\dfrac{m}{3^k},\dfrac{n}{3^k}$ も自然数で同じ方程式を満たすことになるが,$k$ を十分大きくすると $\dfrac{m}{3^k}$ は自然数ではなくなる(いくらでも $0$ に近づく)ので矛盾。よって背理法により題意は示された。

同様にして $p$ が素数なら $\sqrt{p}$ が無理数であることが証明できます。
まあこの問題は通常の背理法を用いて簡単に証明することができるので無限降下法を使う嬉しさはありませんが練習ということで、、

フェルマーの最終定理の $n=4$ の場合の証明

フェルマーの最終定理の $n=4$ の場合:$a^4+b^4=c^4$ を満たす自然数 $a, b, c$ が存在しないこと,を示します。 $x^4+y^4=z^2$ を満たす自然数が存在しないことを言えば十分です。

証明

$x^4+y^4=z^2$ を満たす自然数$(x, y, z)$ が存在すると仮定する。そのような$(x,y,z)$ の組で $z$ が最小のものについて考える。すると,$(x^2, y^2, z)$ の最大公約数は $1$ となる(最大公約数が $d$ なら両辺を $d^2$ で割ることでより $z$ の小さい解を作れる)
$(x^2,y^2,z)$ は最大公約数が1であるピタゴラス数なので互いに素な自然数 $p, q$ を用いて以下のように表せる:
$x^2=p^2-q^2, y^2=2pq, z=p^2+q^2$
よって,1つ目の式から$(x,q,p)$ も最大公約数が1であるピタゴラス数となる(※)ので同様に自然数 $r, s$ を用いて以下のように表せる:
$x=r^2-s^2, q=2rs, p=r^2+s^2\cdots (1)$
以上の方程式から,
$y^2=2pq=4prs$
$p,r,s$ はどの2つをとっても互いに素(※※)なので,それぞれ平方数となる:
$p=a^2,r=b^2,s=c^2$
これらと(1)の第3式を合わせて,
$a^2=b^4+c^4$ となりもとの方程式の新しい解を得られたが,$a\leq p\leq p^2 <z$ より,これは $z$ の最小性に矛盾。

※$(x,q,p)$ の最大公約数が1であることは,「最大公約数が $d$ だと $x^2,y^2,z$ も $d$ 倍数となる」ことから分かる。
※※例えば $p, r$ の最大公約数が $d$ だと $s$ も $d$ の倍数となり,$x,q,p$ が全て $d$ の倍数となる。


無限降下法は数学的帰納法の一種ともみなせます。他のパターンについては数学的帰納法のパターンまとめも参考にしてみてください。

整数問題の証明は細部を丁寧にやるのが難しい

Tag: 数学的帰納法のパターンまとめ
Tag: とにかく美しい数学公式まとめ

分野: 整数問題  レベル: 数学オリンピック