次の文章を完全解説して下さい。
演習問題6
nを1より大きい正の整数とする。nより小さく、nと互いに素な正の整数をa1,a2,・・・,aφ(n)とするとき、次を求めよ。
a1+a2+・・・+aφ(n)=∑((x,n)=1,0≦x<n)x
証明
f(n)=a1+a2+・・・+aφ(n)=∑((x,n)=1)xとおく。
1≦x<nで(x,n)=dなるxの和はdf(n/d)に等しい(定理3.4の証明参照)。dをnの約数全部動かして足せば、0からn-1までの数全部が現れるから、
∑(d|n)df(n/d)=0+1+・・・+(n-1)=n(n-1)/2
ここで、∑(d|n)df(n/d)=∑(d|n)(n/d)f(d)であるから、
∑(d|n)(n/d)f(d)=n(n-1)/2 すなわち、
∑(d|n)f(d)/d=(n-1)/2を得る。反転公式(定理3.7)と定理3.6より、
f(n)/n=∑(d|n){(d-1)/2}μ(n/d)
=(1/2)∑(d|n)(d-1)μ(n/d)
=(1/2)∑(d|n)dμ(n/d)-(1/2)∑(d|n)μ(d)
=(1/2)φ(n)-(1/2)・0=φ(n)/2
∴f(n)=nφ(n)/2
定理3.6
nを自然数とするとき、つぎの式が成り立つ。
∑(d|n)μ(d)=1(n=1)
=0(n>1)
ただし、和はnのすべての正の約数dについての和を表すものとする。
定理3.7(メビュースの反転公式)
F(n),f(d)を整数の集合ℤからℤへの関数とする。このとき、F(n)=∑(d|n)f(d)が成り立てば、
f(n)=∑(d|n)μ(d)F(n/d)が成り立つ。ただし、和はnのすべての正の約数dについての和を表すものとする。
「演習 群・環・体 入門」新妻弘著より
定理3.4
nを自然数とするとき、次の等式が成り立つ。
∑(d|n)φ(d)=n
ここで、和はnのすべての約数についての和を意味するものとする。
証明
S={1,2,・・・,n}とおく。
(1)d1,d2,・・・,dkをnのすべての相異なる約数として
Ai={a∈S|(a,n)=di}(i=1,2,・・・,k)
とおく。aをSの任意の元とする。(a,n)=dとするとdはnの約数であるから、あるdi(1≦i≦k)があってd=di このとき、a∈Ai したがって、
S⊂A1∪・・・∪Ak
各AiはSの部分集合であるから、
S⊃A1∪・・・∪Ak
よって、S=A1∪・・・∪Ak
またAi∩Aj=φとすると、あるaがAi∩Ajに存在する。このとき、a∈Aiより(a,n)=di,a∈Ajより(a,n)=dj ゆえに、di=dj すなわち、i=j したがって、
i≠j⇒Ai∩Aj=φ
以上より、S=A1∪・・・∪Ak,Ai∩Aj=φ(i≠j)
であることがわかった。このことより、
n=|S|=|A1|+・・・+|Ak|を得る。
(2)ni=n/diとすると集合Aiの元の個数はφ(ni)であることを示す。
集合Aiの任意の元をaとすると、(a,n)=diであるから
a=a'idi(a'i,ni∈S)
n=nidi(a'i,ni)=1
と表現される。ここで、di≦a≦nより1≦a'i≦ni よって、
∀a∈Ai,∃a'i∈S,a=a'idi,(a'i,ni)=1,1≦a'i≦ni
と表現される。
逆に、a'iを1≦a'i≦niなる数でniと互いに素であるとすると、このようなa'iによって定まる数a=a'idiはnとの最大公約数がdiとなる。したがって、集合Aiは、
Ai={a'idi|1≦a'i≦ni,(a'i,ni)=1}
と表される。また、
A'i={a'i|1≦a'i≦ni,(a'i,ni)=1}
なる集合を考えると、Aiの元の個数とA'iの元の個数は等しい。ところが、集合A'iの元の個数は1,2,・・・,niのなかでniと互いに素であるものの個数であるから、定義によってオイラーの関数の値φ(ni)に等しい。ゆえに、
|Ai|=|A'i|=φ(ni)
(3)niはn=nidiによって定まる数であるから、{n1,・・・,nk}は{d1,・・・,dk}なる集合と一致する。
以上(1),(2),(3)により、
n=|A1|+・・・+|Ak|=φ(n1)+・・・+φ(nk)=φ(d1)+・・・+φ(dk)
「群・環・体 入門」新妻弘・木村哲三著より
具体的には、
>1≦x<nで(x,n)=dなるxの和はdf(n/d)に等しい(定理3.4の証明参照)。dをnの約数全部動かして足せば、0からn-1までの数全部が現れる
ここは本当に難しいと思います。具体例だけ挙げて確認してスルーしても良いです。(私は今回何とか解読出来たと思います。)
>すなわち、
∑(d|n)f(d)/d=(n-1)/2を得る。反転公式(定理3.7)と定理3.6より、
f(n)/n=∑(d|n){(d-1)/2}μ(n/d)
=(1/2)∑(d|n)(d-1)μ(n/d)
=(1/2)∑(d|n)dμ(n/d)-(1/2)∑(d|n)μ(d)
=(1/2)φ(n)-(1/2)・0=φ(n)/2
∴f(n)=nφ(n)/2
あとはここぐらいですね。
おまけ: