平成１７年７月２４日

[流れ星]

　　　　　第１５７回数学的な応募問題解答

　　　　　　＜解答募集期間：７月３日〜７月２４日

［オイラー関数］

皆さん、オイラー関数って知っていますか。今回はこの性質を利用しながら考えてください。

　「オイラー関数」

問題１　（１）φ（ｎ）＝８を満たす自然数ｎを求めよ。

　　　　（２）φ（ｎ）＝２０を満たす自然数ｎを求めよ。

問題２：１００より小さくて、１００と互いに素なすべての自然数Ｍについて

（１）この自然数Ｍの個数を求めよ。

（２）この自然数Ｍの和を求めよ。

問題３：（１）２０のすべての正の約数ｄについて、φ（ｄ）の値を合計するといくつか。

　　　　（２）１００のすべての正の約数ｄについて、φ（ｄ）の値を合計するといくつか。

　　　　（３）一般に、自然数ｎのすべての正の約数ｄについて、φ（ｄ）の値を合計するといくつか。

ＮＯ１「uchinyan」7/04　13時50分受信

「uchinyan」7/05　12時14分受信 更新7/24　
　題意より、リンクされているオイラー関数φの性質は証明なしに使います。

(一応、後で、証明を試みます。)

なお、オイラー関数φの定義、又は性質の最後の式から

φ(n) = (n 未満で n の約数の倍数でない数の個数)

　　　= (n 以下で n の約数の倍数でない数の個数)

です。

問題1：

一般に、p を素数として、

φ(p^k) = p^k - p^(k-1) = p^(k-1) * (p-1) >= p-1

です。

そこで、p, q, ..., r を素数として、

求める数 n = p^a * q^b * ... * r^c に対して、

φ(n) >= (p-1)(q-1)...(r-1)

になります。

(1)　φ(n) = 8 より、1 <= p <= 9 で、p の候補は、2, 3, 5, 7 です。

p = 7 は、φ(7^k) が 7-1 = 6 で 3 を因数に含んでしまうので不可。

そこで、n = 2^a * 3^b * 5^c になります。

・a, b, c ともに 1 以上の場合

φ(n) = φ(2^a) * φ(3^b) * φ(5^c)

= 2^(a-1) * 3^(b-1) * 5^(c-1) * (2-1) * (3-1) * (5-1)

= 2^(a+2) * 3^(b-1) * 5^(c-1) = 8 = 2^3 で、

a = 1, b = 1, c = 1 となり、n = 2 * 3 * 5 = 30。

実際、

φ(30)

= 30 - 30/2 - 30/3 - 30/5 + 30/(2*3) + 30/(2*5) + 30/(3*5) - 30/(2*3*5)

= 30 - 15 - 10 - 6 + 5 + 3 + 2 - 1 = 8

・c = 0 の場合

φ(n) = φ(2^a) * φ(3^b)

= 2^(a-1) * 3^(b-1) * (2-1) * (3-1) = 2^a * 3^(b-1) = 8 = 2^3 で、

a = 3, b = 1 となり、n = 2^3 * 3 = 24。

実際、

φ(24)

= 24 - 24/2 - 24/3 + 24/(2*3)

= 24 - 12 - 8 + 4 = 8

・b = 0 の場合

φ(n) = φ(2^a) * φ(5^c)

= 2^(a-1) * 5^(c-1) * (2-1) * (5-1)

= 2^(a+1) * 5^(c-1) = 8 = 2^3 で、

a = 2, c = 1 となり、n = 2^2 * 5 = 20。

実際、

φ(20)

= 20 - 20/2 - 20/5 + 20/(2*5)

= 20 - 10 - 4 + 2 = 8

・a = 0 の場合

φ(n) = φ(3^b) * φ(5^c)

= 3^(b-1) * 5^(c-1) * (3-1) * (5-1)

= 2^3 * 3^(b-1) * 5^(c-1) = 8 = 2^3 で、

b = 1, c = 1 となり、n = 3 * 5 = 15。

実際、

φ(15)

= 15 - 15/3 - 15/5 + 15/(3*5)

= 15 - 5 - 3 + 1 = 8

・b = 0, c = 0 の場合

φ(n) = φ(2^a) = 2^(a-1) * (2-1) = 2^(a-1) = 8 = 2^3 で、

a = 4 となり、n = 2^4 = 16。

実際、

φ(16) = 16 - 16/2 = 16 - 8 = 8

・a = 0, c = 0 の場合

φ(n) = φ(3^b) = 3^(b-1) * (3-1) = 2^1 * 3^(b-1) = 8 = 2^3 で、不可。

・a = 0, b = 0 の場合

φ(n) = φ(5^c) = 5^(c-1) * (5-1) = 2^2 * 5^(c-1) = 8 = 2^3 で、不可。

・a = 0, b = 0, c = 0 の場合

φ(n) = φ(1) = 1 で、明らかに、不可。

結局、n = 15, 16, 20, 24, 30。

(2)　φ(n) = 20 より、1 <= p <= 21 で、

p の候補は、2, 3, 5, 7, 11, 13, 17, 19 です。

20 = 2^2 * 5 なので、p 又は p-1 が 2 又は 5 を因数に含む必要があります。

5 を因数に含むのは、p = 5, 11 なので、n は、このいずれかを因数にもつ

必要があります。

・p = 11 の場合

p-1 = 10 なので、φ(n) = 20 = 2 * (11-1) となり、n の他の素因数は、

2 又は 3 だけです。

つまり、n = 2^2 * 11 = 44, n = 2 * 3 * 11 = 66, n = 3 * 11 = 33。

このとき、

φ(44)

= 44 - 44/2 - 44/11 + 44/(2*11)

= 44 - 22 - 4 + 2 = 20

φ(66)

= 66 - 66/2 - 66/3 - 66/11 + 66/(2*3) + 66/(2*11) + 66/(3*11) - 66/(2*3*11)

= 66 - 33 - 22 - 6 + 11 + 3 + 2 - 1 = 20

φ(33)

= 33 - 33/3 - 33/11 + 33/(3*11)

= 33 - 11 - 3 + 1 = 20

・p = 5 の場合

p-1 = 4 なので、φ(n) = 20 = 4 * 5 = 5^1 * (5-1) となり、n の素因数は、2 又は 5 です。

(白状します。最初、素因数 2 の場合を見落としていました。

φ(2) = 1 なので、要注意ですね．．．^^;)

つまり、n = 5^2 = 25 又は n = 2^1 * 5^2 = 50。このとき、

φ(25)

= 25 - 25/5 = 25 - 5 = 20

φ(50)

= 50 - 50/2 - 50/5 + 50/10 = 50 - 25 - 10 + 5 = 20

結局、n = 25, 33, 44, 50, 66。

(考察＆感想)

この問題が一番しんどかったです (^^;

まだ、抜けがないかどうか不安．．．

問題2：

(1)　100 と互いに素、というのは、2, 5 を因数にもたないことなので、

(M の個数) = 100 - 100/2 - 100/5 + 100/10 = 100 - 50 - 20 + 10 = 40

同じことですが、オイラー関数を明示的に使うと、

φ(100) = φ(2^2 * 5^2) = φ(2^2) * φ(5^2)

= 2^1 * (2-1) * 5^1 * (5-1) = 2 * 5 * 4 = 40

(2)　一の位が 1, 3, 7, 9 の数が残っています。そこで、

(M の和)

= 4 * 10 * (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9) + (1 + 3 + 7 + 9) * 10

= 2000

なお、実は、(M の和) = 100 * φ(100) * 1/2 です。考察参照。

(考察)

一般に、n 未満で n と互いに素な自然数を M とすると、

(M の和) = 1/2 * n * φ(n)

になります。証明は簡単です。

M は n と互いに素なので、n - M も n と互いに素です。

M と n - M とは一対一に対応しているので、それぞれ、φ(n) 個あります。

しかも、M + (n - M) = n、(M の和) = ((n - M) の和) なので、

(M の和) = 1/2 * {(M の和) + (M の和)}

= 1/2 * {(M の和) + ((n - M) の和)}

= 1/2 * {(M + (n - M))の和}

= 1/2 * n * φ(n)

問題3：

(1)　20 の約数は、1, 2, 4, 5, 10, 20 で、

φ(1) = 1, φ(2) = 1, φ(4) = 2, φ(5) = 4, φ(10) = 4, φ(20) = 8

そこで、1 + 1 + 2 + 4 + 4 + 8 = 20

(2)　100 の約数は、1, 2, 4, 5, 10, 20, 25, 50, 100 で、

φ(1) = 1, φ(2) = 1, φ(4) = 2, φ(5) = 4, φ(10) = 4,

φ(20) = 8, φ(25) = 20, φ(50) = 20, φ(100) = 40

そこで、1 + 1 + 2 + 4 + 4 + 8 + 20 + 20 + 40 = 100

(3)　(1)及び(2)より、��(d|n)φ(d) = n と思われます。

(ここで、d|n は、d が n を割り切ることを意味します。)

これは、実際、次のようにして証明できます。

・n = 1 のとき

φ(1) = 1 より、明らか。

・n = p, p は素数、のとき

φ(p) = p - 1 = p - φ(1) より、

φ(1) + φ(p) = p で、成立。

・n = p^k, p は素数、のとき

φ(p^k) = p^k - p^(k-1) より、

��(d|n)φ(d)

= φ(1) + φ(p) + φ(p^2) + ... + φ(p^(k-1)) + φ(p^k)

= 1 + (p - 1) + (p^2 - p) ... + (p^(k-1) - p^(k-2)) + (p^k - p^(k-1))

= p^k

= n

で、成立。

・n = p^a * q^b * ... * r^c, p, q, r は素数、のとき

n = p^k のときに成立しているので、

φ(1) + φ(p) + ... + φ(p^(a-1)) + φ(p^a) = p^a

φ(1) + φ(q) + ... + φ(q^(b-1)) + φ(q^b) = q^b

...

φ(1) + φ(r) + ... + φ(r^(c-1)) + φ(r^c) = r^c

これらの両辺を掛け合わせてみます。

0 <= x <= a, 0 <= y <= b, ..., 0 <= z <= c で足し上げるとして、

p^x, q^y, ..., r^z は互いに素だから、

左辺 = �倍φ(p^x)φ(q^y)...φ(r^z)} = �倍φ(p^x * q^y * ... * r^z)}

ここで、p^x * q^y * ... *r^z は、n = p^a * q^b * ... * r^c

の約数です。

つまり、

左辺 = ��(d|n)φ(d)

一方、

右辺 = p^a * q^b * ... * r^c = n

なので、

��(d|n)φ(d) = n

が成立します。

(考察)

これは面白いです！　ちょっと見方を変えて、こんな証明もありますね。

20 = φ(1) + φ(2) + φ(4) + φ(5) + φ(10) + φ(20)

= φ(20/20) + φ(20/10) + φ(20/5) + φ(20/4) + φ(20/2) + φ(20/1)

最後の式の括弧の中の分数の分母も 20 の約数になっています。

つまり、φ(d) = φ(20/e) と見ると、e も 20 の約数で、

d は、20 以下での e の倍数の個数です。

φ(d) は、d 未満で d と互いに素な数の個数ですが、

これを、e * k, 1 <= k <= d, e * d = 20 との関係で見直すと、

k が d と互いに素となる k の個数と見ることができます。

そこで、φ(d) は、e * k と 20 とが e を最大公約数にもつ場合の

e * k の個数と見ることができます。

e * k は 20 以下なので、これは、20 以下の数を 20 との最大公約数、

もちろん 20 の約数、で分類したものの個数、と考えられます。

その個数の総和が先ほどの最後の式ですが、これは、20 以下の数の個数

になるので、当然、20 になります。

具体的に書くと、

20 との最大公約数が 20 の 20 以下の数：1 = φ(20/20) = φ(1) 個

　20 * 1

20 との最大公約数が 10 の 20 以下の数：1 = φ(20/10) = φ(2) 個

　10 * 1

20 との最大公約数が 5 の 20 以下の数：2 = φ(20/5) = φ(4) 個

　5 * 1, 5 * 3

20 との最大公約数が 4 の 20 以下の数：4 = φ(20/4) = φ(5) 個

　4 * 1, 4 * 2, 4 * 3, 4 * 4

20 との最大公約数が 2 の 20 以下の数：4 = φ(20/2) = φ(10) 個

　2 * 1, 2 * 3, 2 * 7, 2 * 9

20 との最大公約数が 1 の 20 以下の数：8 = φ(20/1) = φ(20) 個

　1 * 1, 1 * 3, 1 * 7, 1 * 9,

　1 * 11, 1 * 13, 1 * 17, 1 * 19

というわけで．．．

��(d|n)φ(d) を考えます。

e * d = n とすると、��(d|n)φ(d) = ��(e|n)φ(n/e)。

ここで、m = e * k, 1 <= k <= d なる m を考えると、

φ(n/e) = φ(d) は、k と d とが互いに素、したがって、

m と n とが n の約数 e を最大公約数にもつ場合の m の個数になります。

��(e|n)φ(n/e) は、その総数ですが、m は n 以下なので、

n 以下の数を n の約数 e を最大公約数にもつ場合で分類し、

その個数を足しあげたものです。

しかしそれは、n 以下の数の個数に他ならないので、結局、n になります。

したがって、��(d|n)φ(d) = ��(e|n)φ(n/e) = n です。

なお、もっとナイーブに計算しても証明できそうですが、

一般の場合は大変そうです。原理的には同じだと思うので、

p, q, r を素数として、n = p * q * r の場合だけ、計算してみます。

この場合、約数は、1, p, q, r, pq, qr, rp, pqr = n になります。

φ(n) = n * (1 - 1/p) * (1 - 1/q) * (1 - 1/r)

= n - n/p - n/q - n/r + n/pq + n/qr + n/rp - n/pqr

= n - pq - qr - rp + p + q + r - 1

= n

- pq * (1 - 1/p) * (1 - 1/q) + pq * (1/pq - 1/p - 1/q)

- qr * (1 - 1/q) * (1 - 1/r) + qr * (1/qr - 1/q - 1/r)

- rp * (1 - 1/r) * (1 - 1/p) + rp * (1/rp - 1/r - 1/p)

+ p + q + r - 1

= n - φ(pq) - φ(qr) - φ(rp)

+ (1 - p - q) + (1 - q - r) + (1 - r - p)

+ p + q + r - 1

= n - φ(pq) - φ(qr) - φ(rp)

- p * (1 - 1/p) - q + q * (1 - 1/q) - r + r * (1 - 1/r) - p

+ p + q + r - 1

= n - φ(pq) - φ(qr) - φ(rp) - φ(p) - φ(q) - φ(r) - φ(1)

φ(1) + φ(p) + φ(q) + φ(r) + φ(pq) + φ(qr) + φ(rp) + φ(n) = n

(考察その２)

オイラー関数φの性質を証明しておきます。

(1)　φ(1) = 1

[証明：

これは定義です。

]

(2)　素数 p に対して、φ(p) = p - 1

[証明：

これも定義より明らか。

]

(3)　素数の累乗 p^k に対して、φ(p^k) = p^k - p^(k-1)

[証明：

これも定義より、p^k 未満の p の倍数は、

p * 1, p * 2, ..., p * p^(k-1) の p^(k-1) 個なので、明らか。

]

(4)　m と n が互いに素であるとき、φ(mn) = φ(m)φ(n)

[証明：

定義より、φ(mn) は、mn 未満の mn と互いに素な自然数の個数ですが、

これは m 及び n の両方と互いに素になります。

m と互いに素な自然数は、m の約数を約数にもたない自然数ですが、

これは、m の約数の倍数でない自然数です。

そこで、m の約数の倍数である自然数を考えて、これを除けばいいです。

m の約数の倍数である自然数は、1 〜 m の間に (m - φ(m)) 個あります。

m の約数の倍数である自然数は、m の倍数を境にして周期的に出現するので、

1 〜 mn の間に (m - φ(m)) * n 個あります。

(敢えて倍数を考えたのは、この周期性を利用するためです。)

同様に、n の約数の倍数である自然数は、(n - φ(n)) * m 個あります。

これらは、a * b、a は m の約数又は b は n の約数、となっていますが、

m と n は互いに素なので、a と b も互いの素で、約数同士が交じり合う

ことはありません。

しかし、a は m の約数及び b は n の約数という場合があります。

これは、(m - φ(m)) * (n - φ(n)) 個で、この重複は除く必要があります。

これに注意をすると、

φ(mn)

= mn - (m - φ(m)) * n - (n - φ(n)) * m + (m - φ(m)) * (n - φ(n))

= ... = φ(m)φ(n)

になります。

]

(5)　p, q, ..., r を素数として、n = p^a * q^b * ... * r^c と

素因数分解できるとき

　φ(n) = n * (1 - 1/p) * (1 - 1/q) * ... * (1 - 1/r)

[証明：

p^a, q^b, ..., r^c は互いに素であることから、(4)及び(3)を使って、

φ(n) = φ(p^a * q^b * ... * r^c) = φ(p^a)φ(q^b)...φ(r^c)

= {p^a - p^(a-1)} * {q^b - q^(b-1)} * ... * {r^c - r^(c-1)}

= {p^a * (1 - 1/p)} * {q^b * (1 - 1/q)} * ... * {r^c * (1 - 1/r)}

= (p^a * q^b * ... * r^c) * (1 - 1/p)} * (1 - 1/q) * ... * (1 - 1/r)

= n * (1 - 1/p)} * (1 - 1/q) * ... * (1 - 1/r)]

ＮＯ２「cbc」　　 7/04: 21時55分受信 更新

「cbc」　　 7/17: 12時00分受信 更新7/24

　「解答その１」

　「解答その２」

　

ＮＯ３「kashiwagi」7/11 8時58分受信 更新7/24

　お世話になります。今回の問題は非常に面白く楽しみながら解かせて頂きました。オイラー関数 については初めて知りましたが、オイラーの偉大さを更に増幅認識させて頂きました。しかし、頭の 構造はどうなっているのでしょうか、こんなことを思いつき考えるなんて、正に天才ですね。

　157回解答

問1.

(1) 8=1×8=2×4であるからφ(n)=2,4を探せばよい。オイラー関数の性質1〜5を使い計算するとn=3,4,6でφ(n)=2、n=5,8,10でφ(n)=4となる。

(2) 因って互いに素の数を考えて、

3×5=15,3×8=24,3×10=30,4×5=20,6×5=30(これは重複)及び8=2⁴-2³=φ(2⁴)=φ(16)から求めるｎの値は15,16,20,24,30の5個である。

（2）上記(1)と全く同様の操作を行い求めると、ｎの値は25,33,44,50,66の5個である。

問2.

(1)100=2²×5²であるから100と互いに素な数は2,5及び10の倍数を１〜99の中から引けば良い。

2の倍数は49個、5の倍数は19個そして10の倍数は9個であるから、重複を除外し、59個となる。因って求める個数は99-59＝40個である。

(2)互いに素な数を書き出すと、

　　1,3,7,9

　　11,13,17,19

　　・・・・・・・・・

　　・・・・・・・・・

　　91,93,97,99

であるから求めるものは2000となる。　

問3.

(1) 100=2²×5　であるから約数は全部で3×2=6であり、1,2,4,5,10,20となる。

　因って、φ(1) +φ(2) +φ(4) +φ(5) +φ(10) + φ(20)

=φ(1) +φ(2) +φ(4) +φ(5) (φ(1) +φ(2) +φ(4) )

=(φ(1) +φ(2) +φ(4) )( φ(1) +φ(5))

=(1+1+2)(1+4)=20

(2) 100=2²×5²であるから約数は全部で3×3=9であり、1,2,4,5,10,20,25,50,100となる。

　因って、

φ(1) +φ(2) +φ(4) +φ(5) +φ(10) + φ(20) +φ(25) +φ(50) + φ(100)

= φ(1) +φ(2) +φ(4) +φ(5) (φ(1) +φ(2) +φ(4) ) +φ(25) (φ(1) +φ(2) +φ(4) )

= (φ(1) +φ(2) +φ(4) )( φ(1) +φ(5) +φ(25))

=(1+1+2)(1+4+20)=100

(3)今自然数ｎを因数分解し、以下の様に記述する。ｎ＝ｐ₁^aｐ₂^bｐ₃^c・・・・・ｐ_ｋ^ｋ

　すると上記(1)及び(2)より

Σφ(d)　=　( φ(1) +φ(ｐ₁) +・・・・＋φ(ｐ₁^a))・・・・・・( φ(1) +φ(ｐ_ｋ) +・・・・＋φ(ｐ_ｋ^ｋ))

　　　　　=( 1 +(ｐ₁-1) +・・・・＋(ｐ₁^a-ｐ₁^a-1 ))・・・・・・( 1 +(ｐ_ｋ-1) +・・・・＋(ｐ_k^k-ｐ₁^k-1 ))

　　　　　＝ｐ₁^aｐ₂^bｐ₃^c・・・・・ｐ_ｋ^ｋ＝ｎとなり証明された。

以 上

ＮＯ４「Toru」　　7/12 13時38分受信 更新7/24

　オイラー関数と言えば、割と最近になって、高木貞次著「初等整数論講議」という本を買って読んでいます。値段も少し高めなのと、やっぱり少し古いのかと思って、新しめの他の本を最初は読もうとしていたのですが、やっぱり違いますね、もっと早く買えばよかった。それこそ、２５年ぐらい前に買っていたら、人生が変わっていたかも知れません。　ペンネーム　Toru

問題１
オイラー関数の性質から　nにふくまれる素因数pに対して、p-1がφ(n)の約数になる
ことが必要である。
φ(n)=8　の約数は1,2,4,8  これらに1を加えて素数になるものを選ぶと、p=2,3,5
　よって　n=(2^k)x(3^l)x(5^m) の形でk=0,1,2,3,4、 l=0,1、m=0,1
これらの組み合わせのうち題意を満たすものを選んで、
2x3x5 3x5 2x2x5 2x2x2x3 2x2x2x2 すなわち　
15,16,20,24,30 の５通りが可能
φ(n)=20 の約数は1,2,4,5,10,20 これらに１を加えて素数になるものを選ぶと、
p=2,3,5,11 よってn=(2^q)x(3^r)x(5^s)x(11^t) の形でq=0,1,2,3 r=0,1 s=0,1,2
t=0,1
これらの組み合わせのうち題意を満たすものは
t=1の時　s=0,  t=0の時 s=2 になることに注意して
2x3x11, 2x2x11,3x11,2x5x5,5x5 すなわち
25,33,44,50,66の５通りが可能
問題２
1) φ(100)=φ(2^2x5^2)=100(1-1/2)(1-1/5)=40
2) 自然数M(1≦M≦100) が100と互いに素とすれば,(100-M)も100と互いに素であるか
ら、Mと(100-M)を組にして考えれば、M≠100-Mより、
もとめる和は100xφ(100)/2=2000
問題３
1)２０の約数1,2,4,5,10,20
φ(1)=1 ,φ(2)=1,φ(4)=2,φ(5)=4,φ(10)=4,φ(20)=8
よってΣφ(d)=1+1+2+4+4+8=20
2)１００の約数1,2,4,5,10,20,25,50,100
φ(1)=1,φ(2)=1,φ(4)=2,φ(5)=4,φ(10)=4,φ(20)=8,φ(25)=20,φ(50)=20,
φ(100)=40
よってΣφ(d)=1+1+2+4+4+8+20+20+40=100
3)1≦k≦n の自然数k とnとの最大公約数は、nの約数のいずれかであるから、１〜n
の自然数を、最大公約数で、nの約数のいずれかと対応させて、分類することができ
る。ここでnとkの最大公約数を(n,k)であらわすと (n,k)=d　ならば(n/d,k/d)=1であ
るからdに対応するkの数はφ(n/d)　これをnの全ての約数dについてたしあわせれば、
Σφ(n/d)=n　であるがdがnの全ての約数を動く時n/dもnの全ての約数にわたるから
Σφ(n/d)=Σφ(d)=n

ＮＯ５「浜田明巳」7/12 14時21分受信 更新7/24

　いつものようにエクセルのマクロで解いた．
問題１．
（１）15,16,20,24,30
（２）25,33,44,50,66

問題２．
（１）40
（２）2000

問題３．
　自然数ｎ（１≦ｎ≦５０００）において，φ(ｄ)の合計はｎとなる．
（１）20
（２）100
（３）n

（プログラム）（コピーする際は，全角の空白を縮小の空白に置き直して下さい）
Option Explicit
Const MAX As Integer = 5000
Sub Macro1()
　　Sheets("Sheet1").Select
　　Cells(1, 1).Value = 0
　　Cells(1, 4).Value = 0
　　Range("A1").Select
　　Dim n As Integer
　　Dim nn As Integer
　　Dim retsu As Integer
　　Dim j As Integer
　　For n = 1 To MAX
　　　For j = 1 To 2
　　　　nn = -8 * (j = 1) - 20 * (j = 2)
　　　　retsu = -(j = 1) - 4 * (j = 2)
　　　　If phi(n) = nn Then
　　　　　Cells(1, retsu).Value = Cells(1, retsu).Value + 1
　　　　　Cells(Cells(1, retsu).Value, retsu + 1).Value = n
　　　　End If
　　　Next j
　　Next n
End Sub
Sub Macro2()
　　Sheets("Sheet2").Select
　　Cells(1, 1).Value = 0
　　Cells(2, 1).Value = 0
　　Dim M As Integer
　　For M = 1 To 100 - 1
　　　If GCM(M, 100) = 1 Then
　　　　Cells(1, 1).Value = Cells(1, 1).Value + 1
　　　　Cells(2, 1).Value = Cells(2, 1).Value + M
　　　　Cells(Cells(1, 1).Value, 2).Value = M
　　　End If
　　Next M
End Sub
Sub Macro3()
　　Sheets("Sheet3").Select
　　Dim n As Integer
　　Dim d As Integer
　　For n = 1 To MAX
　　　Cells(n, 1).Value = n
　　　Cells(n, 2).Value = 0
　　　Range("A" & n).Select
　　　For d = 1 To n
　　　　If n Mod d = 0 Then
　　　　　Cells(n, 2).Value = Cells(n, 2).Value + phi(d)
　　　　End If
　　　Next d
　　Next n
　　Range("A1").Select
End Sub
Private Function phi(ByVal n As Integer) As Integer
　　Dim j As Integer
　　If n = 1 Then
　　　phi = 1
　　Else
　　　phi = 0
　　　For j = 1 To n - 1
　　　　phi = phi - (GCM(j, n) = 1)
　　　Next j
　　End If
End Function
Private Function GCM(ByVal a As Long, ByVal b As Long) As Long
　　If b = 0 Then
　　　GCM = a
　　Else
　　　GCM = GCM(b, a Mod b)
　　End If
End Function

NO5「中川幸一」7/24: 11時59分受信 更新7/24

「解答その１」です。

「中川幸一」7/24: 12時24分受信 更新7/24

「解答補足」です。

皆さん、答えがわかったら、一部でも構いませんから、解答とペンネームを添えて、メールで送ってください。待っています。