◆茨城県 小川 康幸 さんからの解答。
まず、補題を３つ、命題を２つ示す。
【補題１】
pを素数とする。任意の自然数mに対して、
mp≡m (mod p)
【証明】
g(m)=mp-mとおく、
g(1)=1-1=0はpで割り切れる。
m=kのとき、g(k)がpで割り切れると仮定する。
1≦i≦p-1のとき、
(i！)*(pCi)=p*(p-1)*･･･*(p-i+1)
i！とpは互いに素だから。pCiはpで割り切れる。
| g(k+1)≡g(k+1)-g(k)= | p-1 Σ i=1 |
{(pCi)*ki}≡0 (mod p) |
よって、g(k+1)もpで割り切れる。
よって、任意の自然数mに対して、mp≡m (mod p)が成立する。
証明終
【補題２】
任意の自然数、mとkと任意の素数pをとる。
mk+p-1≡mk (mod p)が成立する。
【証明】
補題１より
mk+p-1≡(mk-1)*(mp)≡(mk-1)*m≡mk (mod p)
証明終
【補題３】
h(x)を整係数かつ最高次の係数が1のn次式とする。
h(x)≡0 (mod p)の解はn個以下である。
【証明】
n=1のとき
h(x)=x-aだから明らか
n=kのとき正しいと仮定する。
n=k+1のとき
h(x)≡0 (mod p)が解を持たないときは明らかに正しい。
h(x)≡0 (mod p)が解bを持つとき
h(x)=(x-b)*l(x)+h(b)と書ける。
l(x)は、整係数かつ最高次の係数が1の、k次多項式である。
0≡h(x)≡(x-b)*l(x)+h(b)≡(x-b)*l(x) (mod p)
x≡b (mod p) or l(x)≡0 (mod p)
l(x)≡0 (mod p)の解は、帰納法の仮定より、k個以下。
よって、h(x)≡0 (mod p)の解はk+1個以下である。
よって、補題３は示された。
【補題４】
pを素数、lを自然数とする。
l≡1 (mod p-1) ⇔ 任意の自然数mに対して、ml≡m (mod p)となる
【証明】
⇒
l=(p-1)*k+1のとき
補題２より
m(p-1)*k+1≡m(p-1)*(k-1)≡･･･≡mp-1+1≡m (mod p)
逆に、任意の自然数mに対して、ml≡m (mod p)となるとき
lをp-1で割った余りが1でないと仮定する。
l=(p-1)*k+r (2≦r≦p-2)のとき
m≡ml≡m(p-1)*k+r≡m(p-1)*(k-1)+r≡･･･≡mr (mod p)
よって、mr-m≡0 (mod p)がp個の解を持つ事になり、補題３に反する。
またlが(p-1)で割り切れるとき
m≡ml≡m(p-1)*k≡m(p-1)*(k-1)≡･･･≡mp-1 (mod p)
よって、mp-1-m≡0 (mod p)がp個の解を持つ事になり、補題３に反する。
よって、l≡1 (mod p-1)が示された。
証明終
【命題１】
sがある素数pの2乗で割り切れるとき、f(s)=0となる。
【証明】
f(s)≠0となると仮定する。
l=f(s)とおくと、l≧2であるから、
pl≡p (mod m)となるはずだが、
このとき、p≡pl≡0 (mod p2)となって不合理
証明終
【命題２】
sが平方因子を持たないとき、sをs=p1*p2*･･･*ptと素因数分解すると
f(s)=lcm{p1-1,p2-1,･･･,pt-1}
となる。
ただし、lcm{p1-1,p2-1,･･･,pt-1}はp1-1,･･･,pt-1の最小公倍数とする。
【証明】
補題４より
任意の自然数mに対して、
ml≡m (mod pi)となる ⇔ l≡1 (mod pi-1)
よって、
任意の自然数mに対して、
ml≡m (mod pi)となる ⇔ l≡1 (mod lcm{p1-1,p2-1,･･･,pt-1}
)
となる事がわかる。
よって、f(s)=lcm{p1-1,p2-1,･･･,pt-1}となることがわかる。
証明終
命題1、命題２より問題１〜３の解答はこうなる。
【問題１】
f(2)=1, f(3)=2, f(4)=0, f(5)=4, f(6)=2, f(7)=6
【問題２】
f(m)≠0 ⇔ mが平方因数を含まない
【問題３】
命題２より、mをm=p1*p2*･･･*ptと素因数分解すると
f(m)=lcm{p1-1,p2-1,･･･,pt-1}となる。
◆出題者のコメント
小川康幸さん、解答ありがとうございます。
【問題１】,【問題２】,【問題３】とも、すべて正解です。
必要な証明は何１つ省略することなく、しかもその証明が実に鮮やかです。
完璧で期待以上の解答です。
ｍ進表示のときは、ｍの素因数分解での各素数の指数が、すべて１のときだけ ｆ(m)≠０ となり、
それらの各素数より１少ない数たちの最小公倍数が求める ｆ(m) となる。
これって、面白い関係ですよね。