MATH

国立大学入試では前期日程と後期日程が存在する．通常の受験生は前期日程を受けて終わりの人が多いが，残念ながら前期日程で不合格になった人は後期日程を受けることになる（私も前期日程でセンター試験足切り（笑）になって，後期日程を受けました（笑））．

後期試験では前期日程では見られない問題も存在する．小論文が入ったり，問題自体も癖のある問題が出たりする．例えば，明らかに試験中には解かせないような大学の意地のような問題が出たりもする．（1998年，東大，グラフ理論で検索すれば出てくる．暇なときにでも挑戦してみてください．）

一方で，1995年京大の後期日程で次のような面白い問題が出されたことがある．

問題

(京大)

自然数\(n\)の関数\(f(n),g(n)\)を

\(f(n)=n\)を7で割った余り

\(g(n)=3f(\displaystyle \sum_{k=1}^{7}k^{n})\)

によって定める．

(1) すべての自然数\(n\)に対して\(f(n^{7})=f(n)\)を示せ．

(2) あなたの好きな自然数\(n\)を1つ決めて\(g(n)\)を求めよ．その\(g(n)\)の値をこの設問(2)におけるあなたの得点とする．

この問題の面白いところは(2)で\(g(n)\)の値がそのまま得点になるところである．このような問題は今まで見たことないし，非常に難しい問題だ．
さすが自由な大学，京大だわと思った．

(2)は数字を代入していけばゴリ押しで解けるかもしれませんが，ふと思いついた解き方で解いてみました．

解答

(1)

自然数は\(k\)を自然数として，\(7k−6,7k−5,\cdots,7k\)に分けることができる．

それぞれにおいて一般に\(n=7k−p(p=0,1,\cdots,6)\)とすれば，

\(n^{7}=(7k-p)^{7}=7A-p^{7}\)となる．ここで，\(−p\)と\(-p^{7}\)の余りについて考える．

ここで，それぞれの\(p\)の場合について求めれば\(f(n^{7})=f(n)\)となることが分かる．

※法(mod)を知っていればかなり楽に解ける．

(2)

この場合最大は18点となる．なぜなら7で割る余りの最大は6であるからだ．(なおこの問題はおそらく30点分なのでかなり妥当な点数である．)

よって\(f(n)=6\)となる場合が存在するかを調べる．

ここで，余りについて次の等式が成り立つ．

\(f(f(a)+f(b))=f(a+b)\)…①

\(f(f(a)f(b))=f(ab)\)…②

ここで，②より，\(f(n)=f(n^{7})\)\(=f(n\cdot n^{6})=f(f(n)\cdot f(n^{6}))\)

また，②より，\(f(n)=f(n\cdot1)\)\(=f(f(n)\cdot f(1))=f(f(n))\)

よって\(f(n)=f(n)\cdot f(n^{6})-7t\)となる．(\(t\)は整数)

変形して\(f(n)\{f(n^{6})-1\}=7t\)となるが，\(0\leqq f(a)\leqq 6\)より，\(t=0\)のときにのみこの等式が成り立つ．

よって\(f(n)\neq0\)のとき(つまり\(n\neq7\)の倍数)，\(f(n^{6})=1\)となる．

また，①(これを拡張したもの)より，\(f(1^{6}+2^{6}+\cdots 6^{6}+7^{6})\)\(=f(f(1^{6})+f(2^{6})+\cdots+f(6^{6})+f(7^{6}))=6\)

よって\(g(n)=3\times6=18\)となる．

※

①の証明

\(f(x)\)を\(n\)で割った余り，\(a=nX+A,b=nY+B\)とすると，

\(f(a+b)=f(n(X+Y)+A+B)=f(A+B)\)

\(f(f(a)+f(b))=f(A+B)\)である．

②の証明

\(f(ab)=f(n(nXY+AY+BX)+AB)=f(AB)\)

\(f(f(a)f(b))=f(AB)\)である．

※

受験では使えないが，もしフェルマーの小定理を知っていたら…

\(p\)を素数とし，\(a\)と\(p\)は互いに素のとき，

\(a^{p-1}\equiv 1(\bmod p)\)となる．

まず，\(a^{p}\equiv a (\bmod p)\)を証明する．これから上の式は自明となる．

\((m+1)^{p}=m^{p}+_{p}C_{1}m^{p-1}+\cdots+{}_{p}C_{p-1}m+1\) \((m\geqq1)\)

ここで，\({}_{p}C_{k}=\displaystyle \frac{p!}{(p-k)!k!}\)となる．ここで\({}_{p}C_{k}\)は整数で，また\((p−k)!k!\)は\(p\)を因数にもたない．(∵\(p\)は素数)

よって\({}_{p}C_{k}\)は\(p\)を因数にもつ．よって\((m+1)^{p}\equiv m^{p}+1 (\bmod p)\)…①

ここで，\(m=1\)のとき，\(2^{p}\equiv 1^{p}+1\equiv 2 (\bmod p)\)となる．

\(m=k−1\)のときに\(k^{p}\equiv k (\bmod p)\)が成り立つとすると，

\((k+1)^{p}\equiv k^{p}+1\equiv k+1\)(∵①)

これより，\(m=k\)の場合も成り立つ．

以上数学的帰納法より，\(a^{p}\equiv a(\bmod p)\) \((a\geqq2)\)となる．

また，\(a=0,1\)の場合も代入すれば明らかに成り立つ．

これより両者を\(a\)で割ることで，\(a^{p-1}\equiv 1(\bmod p)\)が成り立つ．

これを使うと，\(a^{6}\equiv 1(\bmod 7)\)となる．(ただし，\(a\)と7は互いに素)

よって\(g(6)\)\(=3f(\displaystyle \sum_{k=1}^{7}k^{6})=3f(1^{6}+2^{6}+\cdots+7^{6})\)\(=3f(1^{6}+2^{6}+\cdots+6^{6})\)\(=3f(1+1+\cdots+1)=3f(6)=18\)