n^p≡n(mod p)　フェルマーの小定理

おはようございます。情報セキュリティ・コンサルタントを担当している山田です。
朝、電車の中でFacebookを見ていたら↓の問題が話題になっていました。

 
設問２を見てください。何と自分の点数を自分で決められる問題です。さすが京大。
面白そうなので電車の中で解いてみました。
 
まず設問１のf(n^7)=f(n)の証明は何とかなりそう。
n≡k(mod 7)としてk＝0～6で地道に計算すれば証明できます。合同式を使えばそれほど計算も大変ではありません。
 
そして設問２です。g(1)を試しに計算してみます。
g(1)=3f(1+2+3+4+5+6+7)＝3f(7(7+1)/2))=0
これを選んだら零点。
次に私の好きなラッキーセブンを代入してみます。設問１からg(7)=g(1)なので、g(7)でも零点！
※補足
設問１からf(1^7)=f(1)、f(2^7)=f(2)・・・、f(6^7)=f(6)、f(7^7)=f(7)
g(7)=3f(f(1^7)+f(2^7)+f(3^7)+f(4^7)+f(5^7)+f(6^7)+f(7^7))
=3f(f(1)+f(2)+f(3)+f(4)+f(5)+f(6)+f(7))
=3f(1+2+3+4+5+6+7)=g(1)=0
 
あとは地道に計算なのですが、n=1~7においては、g(6)以外は全て0になりました。
残るg(6)ですが頑張って計算すると、
1^6=1
2^6=(2^3)^2≡1
3^6=(3^2)^3≡2^3≡1
4^6=(2^3)^4≡1
5^6≡(-2)^6=(2^3)^2≡1
6^6≡(-1)^6=1
7^6≡0　より
g(6)=3f(1+1+1+1+1+1+0)=18。やった！18点獲得！これ以上大きな値にはならないので最高点です。
g(8)以降はどうなるのでしょうか。
k^7≡k (mod 7)の両辺にk^(n-1)を掛けると
k^(n+6)≡k^nですね。g(n)は周期6で循環していくようです。
 
小学生の知識（算数）で解ける大学入試問題。しかも自分で自分の得点を決められる。
いつも情報セキュリティのことばかり考えているので良い頭の体操になりました。
＜追記＞
後でネットで調べて分かったのですが、f(n^7)=f(n)はフェルマーの小定理（pが素数の時　n^p≡n(mod p))のp=7の時の式なのですね。数学が苦手な私も漸く思い出しました。

一覧へ