自然数の約数の個数を求めよう【進研模試2012】

模試の解説によく知らない公式が出てきました…。

約数の個数を求める公式のようです。
重要公式なので、これを機に覚えておきましょう!

問題

方程式$7x+3y=1$…①がある。

(1) ①の整数解$(x,y)$を1組求めよ。

(2) ①の整数解$(x,y)$をすべて求めよ。また、①の整数解$(x,y)$に対して$x-y=a$とおくとき、$a$のうち2桁の自然数で最大となるものを求めよ。

(3) (2)で求めた$a$のうち2桁の自然数で最大のものを$M$とする。$M$より小さい自然数のうち、その数の正の約数が6個だけである自然数の個数を求めよ。

得点率は23.2%とのこと。しっかり正答して差をつけたい問題です。

解説

(1)(2)はよくある不定方程式の問題です。特に工夫をせずとも解けると思います。
(3)が今回の焦点です。正の約数を数えるのに、重要な公式を使うことになります。

解を1組求める

不定方程式とは、未知数の数が方程式の数よりも多いような方程式のことです。
解がただ1つに定まらないので「不定」方程式と呼ばれます。

$x$に適当な整数を代入していき、$y$が整数となるような値を探しましょう。

$x=0$のとき、$0+3y=1\Leftrightarrow y=\frac{1}{3}$で不適。
$x=1$のとき、$7+3y=1\Leftrightarrow y=-2$で適。

(1)答

$$(x,y)=(1,-2)$$

これ以外にも、$(-2,5)$や$(4,-9)$など答えは無数にあります。
ただ、あまりに大きい数になると(2)で使いにくくなるので、できるだけ$0$に近い値の組み合わせを探すことをおすすめします。

解をすべて求める

(2)で求めた解は①を満たすので、$$7\times1+3\times(-2)=1$$これを②式とするとき、①-②より、

$$7(x-1)=3(-y-2)$$

$7$と$3$は互いに素です。
すなわちこの式が成り立つためには、$(x-1)$は$3$の倍数、$(-y-2)$は$7$の倍数である必要があります。
式としては、$n$を整数として、

$$\begin{cases}
x-1=3n\\[5pt]
-y-2=7n
\end{cases}$$

となります。これを$x,y$に関して整理すると、

$$\begin{cases}
x=3n+1\\[5pt]
y=-7n-2
\end{cases}$$

これも(1)の答えによって表現のしかたは無数にあって、例えば(1)で$(-2,5)$を求めていた場合には、$(x,y)=(3n-2,-7n+5)$となります。
これは先に示した答えの$n$がちょうど$n-1$に置き換わったような答えです。$n$は任意の整数なので、$x,y$の値としては同じものを指していることになります。


さて、$x-y=a$のとき、

$$(3n+1)-(-7n-2)=a\\
\Leftrightarrow a=10n+3$$

$a$が2桁の自然数で最大(⇔3桁となる直前の自然数)となるのは$n=9$のときで、$a=93$。

(2)答

$\begin{cases}x=3n+1\\[5pt]y=-7n-2\end{cases}$、$a=93$

約数の数を求める

いよいよ約数の個数の話です。
さすがに$1,2,3,…,93$すべての数に対して具体的な約数を出していくわけにはいきませんから、ここで約数の個数に関する公式を利用します。

約数の個数

自然数$N$を素因数分解したとき、$$N=p^aq^br^c…$$と表せるとすると、自然数$N$の正の約数の個数は

$$(a+1)(b+1)(c+1)…$$

一見「どうしてそうなるの?」という形の公式です。
具体例を考えてみましょう。

例えば「$24$」の約数を考えると、$1,2,4,8,3,6,12,24$の8つがあります。
これらを$24$の素因数分解と並べて考えてみます。

$$24=2^3\times3^1$$

$$\begin{align}
1&=2^0\times3^0\\
2&=2^1\times3^0\\
4&=2^2\times3^0\\
8&=2^3\times3^0\\
3&=2^0\times3^1\\
6&=2^1\times3^1\\
12&=2^2\times3^1\\
24&=2^3\times3^1
\end{align}$$

なにやら規則性がありますね。
もとの数を素因数分解したときの素数を何乗分使うか、で約数が決まるのです。

するとその選び方の場合の数は、$2$の指数の選び方が$0$乗から$3$乗の$4$通り、$3$の指数の選び方が$0$乗から$1$乗の$2$通り、掛けて$8$通りと計算できます。

先ほどの公式もやっていることは同じで、$p$の指数の選び方が$0$乗から$a$乗の$(a+1)$通り、$q$の指数の選び方が$0$乗から$b$乗の$(b+1)$通り、…、これらを全て掛けると$(a+1)(b+1)…$通りとなります。


では(3)で求めたい「$M$より小さい自然数のうち、正の約数が6個だけである自然数」を$N$としましょう。

$N$は2桁の自然数なので、$N$の持つ素因数は1~3種類。
(∵4種類以上だと3桁以上となってしまいます。Ex. $2\times3\times5\times7=210>100$)

(i) 素因数が1種類のとき
$N$は素数$p$と自然数$\alpha$を用いて$N=p^\alpha$と書けます。
この$N$の約数の個数は$\alpha+1$個。
これが6個に等しいとき、$\alpha=5\Leftrightarrow N=p^5$。
$p^5<M=93$となる$p$は、$p=2$のみです。

(ii) 素因数が2種類のとき
$N$は素数$p,q\ (p\neq q)$と自然数$\alpha,\beta$を用いて$N=p^\alpha q^\beta$と書けます。
この$N$の約数の個数は$(\alpha+1)(\beta+1)$個。
これが6個に等しいとき、$\alpha=2,\beta=1\Leftrightarrow N=p^2q$。
($\alpha=1,\beta=2$も適ですが、それで得られる$N=pq^2$は$N=p^2q$と同義です。)
$p^2q<M=93$となる$p,q$の組は、
$$\begin{align}
(p,q)=&(2,3),(2,5),(2,7),(2,11),(2,13),(2,17),(2,19),(2,23),\\
&(3,2),(3,5),(3,7),\\
&(5,2),(5,3)
\end{align}$$の13通り。

(iii) 素因数が3種類のとき
$N$は素数$p,q,r\ (p\neq q\neq r\neq p)$と自然数$\alpha,\beta,\gamma$を用いて$N=p^\alpha q^\beta r^\gamma$と書けます。
この$N$の約数の個数は$(\alpha+1)(\beta+1)(\gamma+1)$個。
これが6個に等しくなるような$\alpha,\beta,\gamma$の組は存在しません。

(i)(ii)(iii)の$N$の個数を合計すると、14通り。

(3)答

$14$個

まとめ

約数の個数の公式は忘れたころに登場します。

今回は、任意の自然数の正の約数の個数を求める公式をおさらいしていきました。

公式のポイントをもう一度まとめると、

  • 公式の成り立ちは「もとの自然数の素因数を何回ずつ使うかという場合の数」の計算からきている。
  • 実際に公式を使うときは、場合分けや地道な代入が必要だったりする。

ということでした。
せっかくなので公式の丸暗記ではなく、成り立ちと使い方まで一緒に理解することで応用が利くようにしておきましょう!

それでは。