京大で次のような面白い問題が出されたことがある。
問題
(京大)
自然数nの関数f(n),g(n)を
f(n)=nを7で割った余り
g(n)=
によって定める.
(1) すべての自然数nに対してf()=f(n)を示せ.
(2) あなたの好きな自然数nを1つ決めてg(n)を求めよ.そのg(n)の値をこの設問(2)におけるあなたの得点とする.
この問題の面白いところは(2)でg(n)の値がそのまま得点になるところである。このような問題は今まで見たことないし、非常に難しい問題だ。
さすが京大。一発かましてくれるね!と思った。
解答
(1)
自然数はkを自然数として、7k−6、7k−5、…、7kに分けることができる。
それぞれにおいて一般にn=7k−p(p=0、1、…、6)とすれば、
となる。ここで、−pとの余りについて考える。
ここで、それぞれのpの場合について求めればf()=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)…②
ここで、②より、
よってとなる。(tは整数)
変形してとなるが、より、t=0のときにのみこの等式が成り立つ。
よってf(n)≠0のとき(つまりn≠7の倍数)、となる。
また、①(これを拡張したもの)より、
よって6となるので、これが答えとなる。
※
①の証明
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は互いに素のとき、
となる。
まず、を証明する。これから上の式は自明となる。
ここで、となる。ここでは整数で、また(p−k)!k!はpを因数にもたない。(∵pは素数)
よってはpを因数にもつ。よって…①
ここで、m=1のとき、となる。
m=k−1のときにが成り立つとすると、
(∵①)
これより、m=kの場合も成り立つ。
また、a=0,1の場合も成り立つ。
以上数学的帰納法より、となる。
これよりが成り立つ。
これを使うと、となる。(ただし、aと7は互いに素)
よってg(6)=