Azel's Note

とある高校生の数学ノート。あらゆる問題に対する、感覚と論理の双方向からのアプローチの記録。

京大の整数問題を因数分解だけで解く試み

驚異の本日3投稿目。

夏の間体調を壊し、8月の後半は完全に寝込んでいたので数学から遠ざかってしまっていました。

また体調を崩さないうちに一気に記事を書いています笑。

最近出会ったこんな問題があります。

任意の整数nに対し、n^{9}-n^{3}9で割り切れることを示せ。 (2001年 京都大学)

まあ普通、9を法とした剰余が0になることを言うのでしょう。簡単な問題です。


剰余類を用いた普通の解法

あらゆる整数nは、適当な整数m,k(=-1,0,1)を用いてn=3m+kと表せ、その平方はn^{2}=9m^{2}+6km+k^{2}と表せる。

n^{9}-n^{3}=n^{2}(n-1)n(n+1)(n^{2}+n+1)(n^{2}-n+1)であり、k=0すなわちn=3mのとき、これは9の倍数となる。

n-1,n,n+1のいずれかは3の倍数であるから、k=\pm 1のとき、

(n^{2}+n+1)(n^{2}-n+1)が3の倍数であることが言えればよい。

(n^{2}+n+1)(n^{2}-n+1) \equiv (k^{2}+k+1)(k^{2}-k+1)  \mod 3

k=-1,1のいずれの場合も、これは3の倍数となる。\therefore 題意は示された。


多くの人がこう解くでしょう。

しかし、剰余類を用いてはならないなんてことになったらどうでしょうか。そんなシチュエーションが発生するのかはさておき笑。

一気に難しくなりますが、取りつく島もないわけではありません。

というのも、『連続したm個の整数の積はm!の倍数である』という有明(そして自明)な事実があるからです。

上の解答でもこの事実を用いました。

この事実は、連続したm個の整数のいずれかはmの倍数であり、いずれかはm-1の倍数であり、いずれかはm-2の倍数であり……という考えからわかりますね。

ある数が9で割り切れることを示すには、6!で割り切れることを示せば十分です。6!は9の倍数ですからね。

したがって、ある数を連続した6個の整数の積として表現できれば、その数が9で割り切れることが言えます。

これを利用すれば、実質因数分解のみで解決することも可能かもしれないと思ったので、実際にやってみました。


因数分解による解法

以下では、合同式の法を9とする。

また、連続したm個の整数の積がm!の倍数になる事実を断りなく用いることがある。

n^{9}-n^{3}

=n^{2}(n-1)n(n+1)(n^{2}+n+1)(n^{2}-n+1)

=(n^{2}(n-2)(n-1)n(n+1)(n+2)+n^{2}(n-1)n(n+1)(n+5) )(n^{2}-n+1)

=n^{2}(n-2)(n-1)n(n+1)(n+2)(n^{2}-9-n+10)+n^{2}(n-1)n(n+1)(n+5)(n^{2}-4-n+5)

=n^{2}(n-3)(n-2)(n-1)n(n+1)(n+2)(n+3)-n^{2}(n-2)(n-1)n(n+1)(n+2)(n-10)

+n^{2}(n-2)(n-1)n(n+1)(n+2)(n+5)-n^{2}(n-1)n(n+1)(n+5)(n-5)

\equiv -n^{2}(n-2)(n-1)n(n+1)(n+2)(n-10)+n^{2}(n-2)(n-1)n(n+1)(n+2)(n+5)

-n^{2}(n-1)n(n+1)(n+5)(n-5)

=15n^{2}(n-2)(n-1)n(n+1)(n+2)-n^{2}(n-1)n(n+1)(n^{2}-25)

\equiv -n^{2}(n-1)n(n+1)(n^{2}-4-21)

=-n^{2}(n-2)(n-1)n(n+1)(n+2)+21n^{2}(n-1)n(n+1)

\equiv -n^{2}(n-2)(n-1)n(n+1)(n+2)

=-(n^{2}-9+9)(n-2)(n-1)n(n+1)(n+2)

=-(n-3)(n-2)(n-1)n(n+1)(n+2)(n+3)-9(n-2)(n-1)n(n+1)(n+2)

\equiv 0

よって題意は示された。


一応解決はしましたね笑。整数の連続積を表す記号を考えて導入すれば見かけ上はもうちょっとマシな解答が出来ると思います。

=n^{2}(n-3)(n-2)(n-1)n(n+1)(n+2)(n+3)-n^{2}(n-2)(n-1)n(n+1)(n+2)(n-10)

+n^{2}(n-2)(n-1)n(n+1)(n+2)(n+5)-n^{2}(n-1)n(n+1)(n+5)(n-5)

の次の変形を

\equiv -n^{2}(n-1)n(n+1)(n+5)(n-5)

に留めておいて、n-1 \equiv n+5 \mod 3,n+1 \equiv n-5 \mod 3を用いて(n-1)n(n+1)(n+5)(n-5)が9の倍数であることを示せばここで解答を終えられるのですが、結局気合で計算しきる道を選びました。

まあ、ネタですからね、こんなものは。実用性を求めてはいけない。実際の入試でこういう解き方をした猛者は居るのだろうか。

絶対に二度とやりたくないです。剰余類の有難みが分かりました。