約数の個数と和の求め方:素因数分解から等比数列の和に持ち込もう!

難易度:★★☆☆
頻出度:★☆☆☆

今回は約数の個数と和を求める問題の解き方を解説します。

個数を求めるのは比較的簡単ですが、和を求めるのは案外難しく、等比数列の和を利用します。

一度見ておけば安心なので、是非最後までお付き合いください。

スポンサーリンク

問題に挑戦!

それでは早速例題を見てみましょう。

問題

864の正の約数の個数と和を求めよ。

<解答・解説>

解答を次の図で示し、続いて文章で補足します。

約数の個数と和を求める例題の解答

まずは与えられた数を素因数分解します。

2や3で地道に割っていき、着実に分解しましょう。

なぜ素因数分解するかと言うと、各素数の指数の組み合わせで与えられた数の約数が一意的に決まるからです。

上の解答中で例を示したとおりです。

この「指数の組みあわせで約数が決まる」というのがミソなので、十分に理解しておきましょう。

この点を利用して約数の個数と和を求めます。

約数の個数の求め方

まず、約数の個数は組み合わせの総数に他なりません。

よって各素数の「指数+1を掛け合わせることで求められます。

+1」するのは0乗も含まれるからです。

忘れがちなので注意しましょう。

約数の和の求め方

次に、約数の和はすべての組みあわせの和です。

これを簡単に求めるうまい方法が知られています。

上の解答中に示したように、各素数の0乗、1乗、2乗、… の和をかっこでくくって掛け合わせた式をつくります。

この式を展開すると、もれなくすべての組み合わせの和が出てくるので、約数の和が求められることになります。

ですが実際に展開して計算すると日が暮れてしまうので、等比数列の和の公式を利用します。

各かっこの中身は、初項が1公比が各素数、そして項数が「指数+1の等比数列の和です。

0乗からはじまるので初項が1になり、項数も「+1」になることに注意しましょう。

まとめ

いかがだったでしょうか。

約数の和の求め方は若干トリッキーなので、定石として覚えておくと良いでしょう。

いつものようにまとめを単語カードに書いておきます。

約数の個数と和の求め方のまとめ(1)

約数の個数と和の求め方のまとめ(2)

今回は以上です。

最後までお付き合いいただきありがとうございました!