2015年4月28日

たまに京大の95年後期文系四番が流れてくる.問題文は例えばここで見られるが,大体次のような感じ.

$f(n)$を$n$を$7$で割った余りとする.

  1. $f(n^7) = f(n)$を示せ.
  2. 好きな自然数$n$に対して$g(n) = 3f(\sum_{k = 1}^7k^n)$を計算せよ.その値をこの設問の得点とする.

二つ目の「得点とする」が笑えます.$f$の値は6を超えることはないので,最大18点なわけですが,答えを先に言うと$n = 6$でこの18点を獲得できる.そして,$n = 1,2,3,4,5$では0点となる.何も考えずに最初から計算していくと泣くことになるわけですね…….実はこの「いじわる」は裏があります.以下非数学者向け.KaTeX使ってみたいので書いてみる.

この問題を解く上で,「ある計算結果を$7$で割った余りを求めるには,計算途中で$7$で割った余りに置き換えてよい」ということは知らないとならないだろう.($7$でなくてもよいが.)例えば$10\times 10$を$7$で割った余りを求めるには,まず$10$を$7$で割った余り$3$に置き換えて,$3\times 3= 9$を$7$で割って余り$2$と計算すればよい.もちろん先に計算してもよくて,$10\times 10 = 100 = 7\times 14 + 2$です.(もっと洗練された書き方が合同式.)それを知っていれば,一番は$n = 0,1,2,3,4,5,6$だけでチェックすればよいことがわかる.ちなみに1番はFermatの小定理と呼ばれる定理.

2番は1番を使えということでしょうか.1番はようするに$n^7 - n = n(n^6 - 1)$が$7$で割り切れるということですが,$n$が7の倍数でなければ$n^6 - 1$が$7$で割り切れる,つまり$n^6$を$7$で割った余りが$1$ということ.なので,$n =6$として2を計算すると,$k =7$以外のところは全部余り$1$になり,もちろん$k =7$のところは$0$なので,無事最大値18を達成することができる.

というわけで答えだけならばこれで十分なのですが……何故他は全部$0$になってしまうのか.このからくりは,例えば次のような形で説明できます.例えば$2,4,6,8,10,12$を$7$で割った余りを計算すると$2,4,6,1,3,5$となり,順番は違うけど$1,2,3,4,5,6$となります.なので,さきほどの「計算途中で余りに置き換えてよい」ということから,$f(2^n + 4^n + 6^n + 8^n + 10^n + 12^n) = f(1^n + 2^n + 3^n + 4^n + 5^n + 6^n) = g(n)$です.左辺は$2^n$をくくり出すと,$2^ng(n)$を$7$で割った余りに等しくなります.言い換えると,$(2^n - 1)g(n)$は$7$で割り切れます.例えば$n = 1$だと$g(1)$が$7$で割り切れることになって,よって$g(1) = 0$です.$n = 2,4,5$でも$2^n - 1$は$7$の倍数ではないので,$g(n)$が$7$の倍数にならないといけなくて,$g(n) = 0$となります.$n = 3$ではこれはうまく行きませんがが,2の代わりに3を使うとやっぱり$g(3) = 0$となります.

本当でしょうか.$3,6,9,12,15,18$を$7$で割った余りは,(順番は違うけど)$1,2,3,4,5,6$になるのでしょうか?そうならなかったとしましょう.どっちも六個ずつなので,$3,6,9,12,15,18$を$7$で割った余りには重なりが出ることになります.少し数式を使ってそれが$3k$と$3l$だったとしましょう.$k,l$は$1,2,3,4,5,6$のどれかです.$3k$と$3l$を$7$で割った余りが一緒なので,$3(k - l)$は7で割り切れます.よって$k - l$は7で割り切れます.これは$k = l$でないと無理です.

と言うわけで,$f(k^n)$が全部1でない限り0点しか取れないわけです.$k = 3$でやってみるとわかりますが,$3^1,3^2,3^3,3^4,3^5$,どれも7で割った余りは1になりません.$7$でなくても同じで,一般に素数$p$に対してある$k$が存在して,$k^1,k^2,\ldots,k^{p - 2}$を$p$で割った余りは1になりません(原始根の存在定理).ちなみに$k^{p - 1}$を$p$で割った余りは,$k$が$p$の倍数でなければ1になります(Fermatの小定理).というわけでこの問題は「いじわる」になる.

いわゆる指標の直交性と言うやつです.$G$を可換群,$F$を体,$\chi\colon G\to F^\times$を準同型写像とすると,$\sum_{g\in G}\chi(g)$は全ての$g \in G$に対して$\chi(g) = 1$である時に限り$G$の元の数で,そうでなければ$0$になります.$G = F_7^\times$($F_7$は位数$7$の有限体),$F = F_7$,$\chi(x) = x^n$の時が上.まぁ小難しい話はいいですね…….

0 件のコメント:

コメントを投稿

コメントの追加にはサードパーティーCookieの許可が必要です