約数の個数と和 ［2016 慶應大・理工］

イズミの解答への道

　約数の個数と和に関する基本問題です。これは基礎テク！ですから、解法を覚えておきましょう。

解答

　2016を素因数分解すると、
　　2016 = 2⁵×3²×7
であるから、約数の個数は
　　( 5 + 1 )×( 2 + 1 )×( 1 + 1 ) = 6×3×2=36個
であり、その和は
　　( 1 + 2 + 2² + 2³ + 2⁴ + 2⁵ ) × ( 1 + 3 + 3² ) × ( 1 + 7 ) = 63 × 13 × 8
となるので、その平均は、
　　
である。

解説

約数の個数と和

　自然数 N が
　　N = p^aq^b…r^c
と因数分解できるとする。このとき、すべての約数は、
　　p^a’q^b’…r^c’
の形で表され、a’ , b’ , … , c’ はそれぞれ
　　a’ = 0 , 1 , … , a のいずれか
　　b’ = 0 , 1 , … , b のいずれか
　　c’ = 0 , 1 , … , c のいずれか
の場合が考えられる。存在する約数はこれらのすべての場合の数であるから、
　　( a + 1 ) ( b + 1 ) … ( c + 1 )個
である。
　次に和について考える。和についてはトリッキーな“うまい方法”がある。突然だが、
　　( 1 + p + … + p^a ) ( 1 + q + … + q^b ) … ( 1 + r + … + r^c )
という式を展開すると、最も小さい約数である 1 から、最も大きい約数（自分自身）までのすべての約数が現れる。これにより、約数の和は上の式で求められることが分かる。

【約数の個数と和】
　自然数 N が N = p^aq^b…r^c と因数分解できるとき、約数の個数は、
　　( a + 1 ) ( b + 1 ) … ( c + 1 )個
であり、その約数の総和は、
　　( 1 + p + … + p^a ) ( 1 + q + … + q^b ) … ( 1 + r + … + r^c )
となる。

例題

　基礎的な問題なので毎年どこかの大学では出題されている。

【解答】
　2000 = 2⁴・5³ であるから、約数の個数は、
　　( 4 + 1 )・( 3 + 1 ) = 20個
であり、その和は
　　( 1 + 2 + 2² + 2³ + 2⁴ )・( 1 + 5 + 5² + 5³ )
　　= 31×156 = 4836