第１３８問の解答
１．問題 ［整数、場合の数］
|
大きさが１より小さく、分母が１００１である全ての既約分数の合計は、 |
２．解答例１(ταροさん、C-Dさん、トトロ＠Ｎさん、長野美光さん、ありっちさん、香川仁志さん、有無相生さん、大岡敏幸さん、他多数)
分子について考えることにします。
１００１＝７・１１・１３なので、既約分数の分子は７、１１、１３とそれぞれ互いに素となります。
互いに素な整数を数えるのは面倒なので、替わりに７、１１、１３のいずれかの倍数となる整数を数えることにします。
１から１００１までの整数の中には、７・１１・１３＝１００１の倍数はありません。
上図から、７の倍数と１１の倍数と１３の倍数を加えると、７・１１の倍数、７・１３の倍数、１１・１３の倍数を重複して数えていることになります。従って、７、１１、１３のいずれかの倍数の和＝
７の倍数の和＋１１の倍数の和＋１３の倍数の和
−（７・１１の倍数の和＋７・１３の倍数の和＋１１・１３の倍数の和）7の倍数の和＝7・（1001/7）・（1001/7−1）/2＝71071
11の倍数の和＝11・（1001/11）・（1001/11−1）/2＝45045
13の倍数の和＝13・（1001/13）・（1001/13−1）/2＝38038
7・11の倍数の和＝7・11・（1001/7・11）・（1001/7・11−1）/2＝6006
7・13の倍数の和＝7・13・（1001/7・13）・（1001/7・13−1）/2＝5005
11・13の倍数の和＝11・13・（1001/11・13）・（1001/11・13−1）/2
＝3003よって、７、１１、１３のいずれかの倍数の和
＝71071+45045+38083−（6006+5005+3003)
＝1401401から1000までの整数の和＝1000・1001/2＝500500だから
互いに素な整数の和＝500500−140140=360360よって、規約分数の和＝360360/1001=360となります。
答：３６０
以上
３．解答例２(ヒデー王子さん、清川育男さん、柚奇神太郎さん、他多数)
解答例１で、n=1001、p=7、q=11、r=13とおきます。
今度は、１からn=1001までの整数で考えます。
mの倍数の個数をN(m)、倍数の和をS(m)とします。N(m)＝n/m、Ｓ(m)＝m・（n/m）・（n/m+1）/2となります。
従って、p、q、rのいずれかの倍数の個数
＝N(p)+N(q)+N(r)−（N(pq)+N(pr)+N(qr))+N(pqr)
＝qr+pr+pq-(r+q+p)+1
よって、互いに素な整数の個数
＝pqr-(pq+qr+rp)+(p+q+r)-1
＝(p-1)(q-1)(r-1) ・・・（１）
となります。また、p、q、rのいずれかの倍数の和
＝S(p)+S(q)+S(r)−（S(pq)+S(pr)+S(qr))+S(pqr)
＝n{(qr+1)/2+(pr+1)/2+(pq+1)/2}-n{(r+1)/2+(q+1)/2+(p+1)/2}+n
＝n{qr+pr+pq-(r+q+p)+1}/2
よって、互いに素な整数の和
＝n(pqr+1)/2-n{(pq+qr+rp)+(p+q+r)-1}/2
＝n(p-1)(q-1)(r-1)/2
従って、規約分数の和
＝{n(p-1)(q-1)(r-1)/2}/n
＝(p-1)(q-1)(r-1)/2
＝6・10・12/2
＝360 となります。
４．解答例３(noetherさん、他)
（１）は、一般にオイラー関数と呼ばれ、
自然数nでnと互いに素な自然数の個数をφ(n)、
n=paqbrc・・・と素数巾の積に分解されるとき、
φ(n)=n(1-1/p)(1-1/q)(1-1/r)・・・
と表されます。
このオイラー関数を適用すれば、
φ(pqr)=pqr(1-1/p)(1-1/q)(1-1/r)
=(p-1)(q-1)(r-1)=720
と求まります。ここで、１からn以下の整数mがnと互いに素ならn-mとnも互いに素であることに着目します。
なぜなら、もしmとnが互いに素で、n-mとnが公約数sを持つとしたら、
n-m=st、n=suと表せます。
すると、m=n-st=s(u-t)となり、mとnが共通な公約数sを持つことになり、矛盾。逆も同様。
よって、N=互いに素な整数の個数、Ｓ＝互いに素な整数の和とすると、
Ｓ＝s1+s2+・・+sN（s1+sN=s2+sN-2=・・）と表せます。
2Ｓ＝(s1+s2+・・+sN)+（sN+sN-1+・・+s1)
＝(s1+sN)+(s2+sN-2)+・・(sN+s1)
＝nN
よって、S=nN/2となります。
これから、規約分数の和＝S/n=N/2=360と求まります。
