【標準】約数の個数、約数の和

🕒 2017/01/28 🔄 2023/05/01

ここでは、約数の個数や約数の和を求める問題を考えていきます。【標準】和集合の要素の個数などで倍数の個数を数えたことはありましたが、約数の個数はまた違った考え方が必要になります。一度知ると、簡単に求められるようになります。

📘 目次

約数の個数

例題

24の正の約数は何個あるか。

まずは、具体的に書き出してみましょう。\[ 1,2,3,4,6,8,12,24 \]の8個ですね。小さい方から順番に割り切れるかどうかをチェックしていけば、すべてを書き出すことは可能です。しかし、数が増えてくると、書き出すのは大変です。

【基本】集合の要素の個数で倍数の個数を数えるとき、「2×〇」などという形にすると考えやすくなりました。今の場合でも使ってみましょう。上の約数を、素因数分解して書き直してみると次のようになります。\[ 1,\ 2,\ 3,\ 2^2,\ 2\times 3, \\ 2^3,\ 2^2\times 3,\ 2^3\times 3 \]まだちょっとわかりにくいですね。2の何乗かで分類して書いてみましょう。
\begin{eqnarray} & & 1 &,& \ 3, \\ & & 2 &,& \ 2\times 3, \\ & & 2^2 &,& \ 2^2\times 3, \\ & & 2^3 &,& \ 2^3\times 3 \end{eqnarray}こう書くと、結構規則性が分かってきたのではないでしょうか。さらに書き直してみます。 $2$ や $3$ も「〇乗」の形で書いてみます。また、 $2^0=3^0=1$ という変形も使ってみます。 $2^0=1$ は本来はここの分野で学ぶことではありませんが、 \begin{eqnarray} & 2^3 & \rightarrow & 2^2 & \rightarrow & 2^1 & \rightarrow & 2^0 \\ & 8 & \rightarrow & 4 & \rightarrow & 2 & \rightarrow & 1 \\ \end{eqnarray}と右上の数字が1減るごとに2で割られていく流れから理解できると思います。このことを利用して上の約数を書き直すと、 \begin{eqnarray} & & 2^0 \times 3^0 &,& \ 2^0 \times 3^1, \\ & & 2^1 \times 3^0 &,& \ 2^1 \times 3^1, \\ & & 2^2 \times 3^0 &,& \ 2^2 \times 3^1, \\ & & 2^3 \times 3^0 &,& \ 2^3 \times 3^1 \end{eqnarray}となります。このことから、約数は、 $2$ の右上の数字が $0$ から $3$ までの4通り、そのそれぞれに、 $3$ の右上の数字が $0$ か $1$ の2通りあることがわかります。よって、約数の個数は\[ 4\times 2 = 8 \]個と求められます。

$24=2^3\times3^1$ と素因数分解でき、各素因数について、 $0$ から右上の数字までの選び方があるということです。他の例でも考えてみましょう。 $360$ ならば、 $360=2^3\times 3^2 \times 5$ と素因数分解できるので、正の約数は $2^a\times 3^b \times 5^c$ の形で書けます。 a は $0$ から $3$ までの4通り、b は3通り、 c は2通りあるので、正の約数は\[ 4\times 3 \times 2=24 \]個となります。書き出さなくても、計算で出せるので楽ですね。

ここまでのことを一般的に書くと、次のようにまとめられます。文字がたくさん出てきますが、やっていることは同じです。

約数の個数

自然数 N が\[ N=p_1^{a_1} \cdot p_2^{a_2} \cdots p_m^{a_m} \]と因数分解できるとき、 N の正の約数の個数は、次で求められる。\[ (a_1+1)(a_2+1)\cdots(a_m+1) \]

約数の和

約数の個数と関連して、約数の和も簡単な計算で求められます。例えば、24の正の約数の和を考えてみましょう。素因数分解をした形で和を考え、因数分解すると次のようになります。
\begin{eqnarray} & & 2^0 \times 3^0 + \ 2^0 \times 3^1 \\ & &+ 2^1 \times 3^0 + \ 2^1 \times 3^1 \\ & &+ 2^2 \times 3^0 + \ 2^2 \times 3^1 \\ & &+ 2^3 \times 3^0 + \ 2^3 \times 3^1 \\[5pt] &=& (2^0+2^1+2^2+2^3) \times 3^0 \\ & & +(2^0+2^1+2^2+2^3) \times 3^1 \\[5pt] &=& (2^0+2^1+2^2+2^3)(3^0+3^1) \\[5pt] &=& 15 \times 4 \\[5pt] &=& 60 \end{eqnarray}最後の掛け算を計算するのは、すべて足すよりもだいぶ楽になると思います。この計算方法は一般的な場合でも応用でき、次のようにまとめることができます。

約数の和

自然数 N が\[ N=p_1^{a_1} \cdot p_2^{a_2} \cdots p_m^{a_m} \]と因数分解できるとき、 N の正の約数の和は、次で求められる。
\begin{eqnarray} & & (1+p_1+p_1^2+\cdots +p_1^{a_1}) \\ & & \times (1+p_2+p_2^2+\cdots +p_2^{a_2}) \\ & & \times \cdots \\ & & \times (1+p_m+p_m^2+\cdots +p_m^{a_m}) \\ \end{eqnarray}

展開すると、すべての正の約数が出てくることから、成り立つことがわかります。

例えば、 $360$ であれば、 $360=2^3\times 3^2 \times 5$ と素因数分解できるので、正の約数の和は
\begin{eqnarray} & & (1+2+2^2+2^3)(1+3+3^2)(1+5) \\ &=& 15\times 13\times 6 \\ &=& 1170 \end{eqnarray}と求められます。24個の約数を足すよりも楽ですね。