数列 を次のように定める。
(1) 正の整数 が の倍数のとき， は の倍数となることを示せ。
(2) , を正の整数とする。 が の倍数となるための必要十分条件を , を用いて表せ。
(3) と の最大公約数を求めよ。
, , , , と、数はすぐ手に負えなくなります。そのまま追うのはあきらめて、余りだけを見ます。
は、 の余りだけで次の余りが決まる形です。だから余りは必ずどこかでめぐり始めます。
で割った余りを並べると , , , , , , です。 の次は で先頭へ戻り、 つでひと回りします。
余りが になるのは 番目、 番目、 ですから、 が の倍数になるのは が の倍数のときです。これで (1) が示せました。
こんどは で割った余りを見ます。 ですから です。先頭に戻りました。
先へも続きます。 なら ですから、 が について次々に出ます。
つまり で割った余りは 個ごとに同じ並びをくり返し、 が出るのは添字が の倍数のところだけです。
途中で が出ないことも要ります。 では ですから、余りは そのもので になりません。(2) の答えは「 が の倍数であること」です。
(3) では つの添字がどちらも大きく、片方は 乗されています。まず 乗を外して考えます。
を で割った余りを とすると、いまの性質から です。だから となります。
これは添字のほうでユークリッドの互除法を回すのと同じことです。行き着く先は です。
、 ですから で、 です。
と が共通に持てる素数は、 と の両方を割る素数だけです。それは に限られます。
残るのは を何個まで共通に持てるかです。 の側は 乗したぶん増えているかもしれません。
で割った余りを追います。, , , , , , と、こちらも つでめぐります。 の倍数のところは余りが で、 ではありません。
つまり は で割れますが では割れず、 を 個しか持ちません。少ないほうに合わせるので、最大公約数は です。