問題
とする．
(1) で，，，ならば，，が成立することを示せ．
(2) ，がをみたす自然数ならば，ある自然数をとるととなることを示せ．
出典：京都大学 1988年度 前期日程 第2次学力試験 理系 第3問
方針
変換を成分で 、 と書く。まず を直接計算で確認する。次に から を導き、 を示す。(2)ではこの操作を繰り返すと非負整数 が真に減少するので有限回で となり、そのとき になる。
解答
(1)
変換後の成分を と書く。直接計算すると
である。したがって ならば である。
次に の範囲を調べる。条件より であり、、 だから である。また が で成り立つので である。よって となり、 である。
(2)
が自然数で を満たすとする。 の間は、(1)により変換後も を満たし、しかも である。さらに についても正であることを確認しておく。実際、 かつ より なので である。
したがって、この変換を繰り返すと、第2成分は非負整数のまま真に小さくなる。無限に小さくなり続けることはできないので、有限回で第2成分は0になる。そのとき第1成分を とすれば であり、しかも第1成分は正なので である。
よって、ある自然数 について、問題の行列表示で すなわち、問題文の等式が成り立つ。
補足。この証明は、解を小さい解へ下げていく降下法である。保存される量は 、小さくなる量は であり、この2つを同時に確認することで有限回で に到達する。