目次
代数系入門 (松坂和夫) 第1章 §8 問題2 の解答です。
この性質はよく知られているもので、 (代数系入門 (松坂和夫) には解答がありませんが) 割とよく解法を目にします。
命題
( varphi ) をオイラー関数とするとき、 任意の ( n in mathbb{Z}^{+} ) について次の式が成り立つ。
[ sum_{d|n} varphi(d) = n ]試してみる
試しに 約数の多い 24 について調べてみます。 ヒントには ( (x, n) = d ) となる ( x ) の個数を考えよとありますね。
| ( (x, n) = d ) なる ( x ) | ( d ) | ( d ) と互いに素な数 |
|---|---|---|
| 47, 43, 41, 37, 31, 29, 25, 23, 19, 17, 13, 11, 7, 5, 1 | 1 | 1 |
| 46, 38, 34, 26, 22, 14, 10, 2 | 2 | 1 |
| 45, 39, 33, 27, 21, 15, 9, 3 | 3 | 1, 2 |
| 44, 28, 20, 4 | 4 | 1, 3 |
| 42, 30, 18, 6 | 6 | 1, 5 |
| 40, 8 | 8 | 1, 3, 5, 7 |
| 36, 12 | 12 | 1, 5, 7, 11 |
| 32, 16 | 16 | 1, 3, 5, 7, 9, 11, 13, 15 |
| 24 | 24 | 1, 5, 7, 11, 13, 17, 19, 23, 24, 29 |
| 48 | 48 | 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47 |
表の左と右の数の個数が対照的になっているのがわかるでしょうか。
証明
ある ( n ) の約数 ( d ) について ( A_d = left{ m in mathbb{Z} | 1 leq m leq n, ( m, n ) = d right} ) と定義します。
すべての ( d ) を考えれば、 ( n ) 以下 の任意の数 ( x ) について ( x in A_d ) なる ( d ) が存在します。 もし ( x ) が ( n ) との約数をもてば、 その約数のうち一番大きいものが ( d ) となりますし、 約数をもたなければ ( d = 1 ) となります。
ここで ( (m, n) = d ) なる数 ( m ) について、 ( frac{m}{d} ) と ( frac{n}{d} ) は互いに素です、最大公約数で割っていますから。 また逆に 任意の ( n ) の約数 ( d ) について ( frac{n}{d} ) と互いに素な数 ( frac{m}{d} ) を考えた時、 ( (m, n) = d ) となります。
[ (m, n) = d Leftrightarrow frac{m}{d}, frac{n}{d} in mathbb{Z}, frac{m}{d} perp frac{n}{d} ]これにより、 ( A_d ) の要素数 ( | A_d | ) は ( varphi left( frac{n}{d} right) ) と等しくなります。
[ | A_d | = varphi left( frac{n}{d} right) ]( d_1, d_2 ) を ( n ) の約数としたとき、 ( x in A_{d_1} ) と ( x in A_{d_2} ) は同時に成立しないため、
[ n = sum_{d|n} | A_d | = sum_{d|n} varphi left( frac{n}{d} right) ]となります。
ここで ( frac{n}{d} ) の集合は ( d ) の集合に等しいですから
[ n = sum_{d|n} varphi left( frac{n}{d} right) = sum_{d|n} varphi(d) ]となります。
