「約数リスト」の決定問題

2つの整数$${a,b}$$について$${a=bc}$$となる第三の整数$${c}$$が存在するとき、$${b}$$は$${a}$$の約数と呼ばれ、$${b}$$は$${a}$$を割り切るなどと呼ばれます。$${b}$$が$${a}$$の約数なら、$${-b}$$も$${a}$$の約数なので、約数について調べるには$${0}$$以上の約数だけを調べれば十分です。整数$${a}$$の約数で$${0}$$以上のものの全体がなす集合を$${D^+(a)}$$と書いて、$${a}$$の約数リストと呼ぶことにします。

与えられた整数の約数リストを求めることは、初等整数論の基本的な問題だと思います。例えば、2つの整数$${a,b}$$について、$${D^+(a)}$$と$${D^+(b)}$$の共通部分$${D^+(a)\cap D^+(b)}$$は、$${a,b}$$の公約数リストです。以前書いた https://note.com/katobungen/n/nb20d1c15ea2c でも述べたように、$${a,b}$$の最大公約数とは、

$$
D^+(a)\cap D^+(b)=D^+(d)
$$

となる$${0}$$以上の整数$${d}$$のことです。

自然数$${a}$$の約数リスト$${D^+(a)}$$を求める素朴で確実な方法は、$${1,2,3,\ldots,a}$$で順々に$${a}$$を割り算して、割り切れるものだけを$${D^+(a)}$$に入れるという方法です。この方法は確実でわかりやすいですが、$${a}$$のサイズが大きくなると、だんだん計算が大変になってきます。

もう少し賢い方法は、素因数分解を使うというものです。高校数学でも、次のような定理が紹介されることがあります。

定理．$${0}$$でない整数$${a}$$の素因数分解が
　　$${a=\pm p^{e_1}_1p^{e_2}_2\cdots p^{e_r}_r}$$
（$${p_1,p_2,\ldots,p_r}$$は互いに相異なる素数）で与えられているとき、$${a}$$の任意の約数は
　　$${\pm p^{f_1}_1p^{f_2}_2\cdots p^{f_r}_r}$$
（ただし、$${0\leqq f_1\leqq e_1,0\leqq f_2\leqq e_2,\ldots,0\leqq f_r\leqq e_r}$$）で与えられる。特に$${a}$$の正の約数の個数は
　　$${(e_1+1)(e_2+1)\cdots (e_r+1)}$$
で与えられる。

（上の定理は$${a=\pm 1}$$の場合も$${r=0}$$として含んでいます。）

もちろん、これは高校数学でも紹介されるくらいですから、当然正しいのですが、これで約数リストが完全に求められることを示すには、実は極めて非自明な事実を使わなければなりません。すなわち、次の2つのことを示す必要があります。

示すべきこと．
① $${a}$$のどんな約数も$${\pm p^{f_1}_1p^{f_2}_2\cdots p^{f_r}_r}$$（$${0\leqq f_1\leqq e_1,0\leqq f_2\leqq e_2,\ldots,0\leqq f_r\leqq e_r}$$）という形に必ず書けること。
② $${\pm p^{f_1}_1p^{f_2}_2\cdots p^{f_r}_r}$$（$${0\leqq f_1\leqq e_1,0\leqq f_2\leqq e_2,\ldots,0\leqq f_r\leqq e_r}$$）というリストにダブりがないこと。

この2つの主張は、どれも「初等整数論の基本定理」、すなわち素因数分解の存在と一意性を使わなければ証明できません。特に、一意性が重要です。そして素因数分解の一意性の証明は、これまたかなり非自明です。それは素数の定義だけからでは示すことができません。具体的には、素数の素元としての性質「$${p|ab}$$ $${\Rightarrow}$$ $${p|a}$$または$${p|b}$$」を使わなければなりませんが、この性質は素数の定義からすぐにわかることだと思い込んでいる人が多い（さすがに数学の研究者にはいないと思いますが）ようです。