思いつきます？

「１０００以下の自然数のうち、約数が５個であるものをすべて答えよ」という問題がわからずに、解説を見ました。

すると、

【約数が５個である自然数ｘの約数は
１,a,a^2,a^3,ｘ（aは素数。ｘはa^4）であるので、
答えは
２^4＝１６
３^4＝８１
４^4＝２５６
である。】

とありました。

この回答、どうすれば「約数が５個である自然数ｘの約数は
１,a,a^2,a^3,ｘ（aは素数。ｘはa^4）である」
なんて思いつくのでしょう？
とっても不思議です。

No.6 ベストアンサー 回答者： liar_adan 回答日時： 2004/01/12 21:05

整数nを

n = 2^k1 * 3^k2 * ... * Pm^km
(Pmはm番目の整数、k1~kmは整数)
と素因数分解します。
すると、「約数の数」は
(k1+1) * (k2+1) * ... * (km+1)
となります。

たとえば
18 = 2^1 * 3^2
を考えてみると、約数は

1 = 2^0 * 3^0
2 = 2^1 * 3^0
3 = 2^0 * 3^1
6 = 2^1 * 3^1
9 = 2^0 * 3^2
18 = 2^1 * 3^2

となります。
(各素数の乗数が、0からkmまで揃うわけですね)

ここで、「約数が5」ということから、
二つ以上の素数が約数になることはできません。
5自体が素数なので、分解できませんから。
だから、ひとつの素数の累乗である数で、
しかも4乗、ということがわかるのです。

蛇足ですが＃５さんの
＞２つ以上の別の素数を約数に持つ自然数の、約数の数は必ず偶数になります。
というのは違います。
たとえば
36 = 2^2 * 3^2
の約数の数は、(2+1)*(2+1)で9個です。

No.14 回答者： kony0 回答日時： 2004/01/14 00:13

> (p1+1)*(p2+1)*(p3+1)*(p4+1)*・・・*(pn+1)=5

> この式では約数の個数を求められない様な気がしてきましたので却下。

この式から、piのどれか１つだけが４、他はすべて０であることが言えます。（all piが非負整数という仮定の元で）

No.13 回答者： arukamun 回答日時： 2004/01/13 11:46

たびたび

＞自分のNo.2の回答で
＞＞p1+p2+p3+p4+・・・+pn=4
＞が間違っていたからもっと存在すると思っちゃった訳ですね。(笑)
＞(p1+1)*(p2+1)*(p3+1)*(p4+1)*・・・*(pn+1)=5
＞で5は素数なので、何れか一つの素数の項だけが２以上で、それ以外は１という事になるわけですね。
(p1+1)*(p2+1)*(p3+1)*(p4+1)*・・・*(pn+1)=5
この式では約数の個数を求められない様な気がしてきましたので却下。

No.12 回答者： arukamun 回答日時： 2004/01/12 23:40

自分のNo.2の回答で

＞p1+p2+p3+p4+・・・+pn=4
が間違っていたからもっと存在すると思っちゃった訳ですね。(笑)
(p1+1)*(p2+1)*(p3+1)*(p4+1)*・・・*(pn+1)=5
で5は素数なので、何れか一つの素数の項だけが２以上で、それ以外は１という事になるわけですね。

おもしろい問題をありがとうございます。

No.11 回答者： kater_kurz 回答日時： 2004/01/12 23:29

整数論をやってるような方にとっては殆ど自明なのかもしれませんが、「知識」と言ってしまうとみもふたもないので、原始的に考えてみました。

背理法で素因数の種類を絞って行くのが判りやすいかと思います。

求める自然数をxと置く。

(i)
xは1と素数でないx自身を約数として持つから、xの素因数は３種類以下である。

(ii)
xの素因数が３種類だと仮定すると、xの約数は、
1,p1,p2,p3,p1*p2*p3
と置けるが、このとき、p1*p2もxの約数となり矛盾。
よって、xの素因数は２種類以下。

(iii)
xの素因数が２種類だと仮定すると、xの約数は、
1,p1,p2,p1*p2,p1*p2*P1*p2
と置けるが、このとき、p1^2*p2もxの約数となり矛盾。
よって、xの素因数は１種類のみ。

(iii)
xの素因数が１種類のみのとき、xの約数は、
1,p1,p1^2,p1^3,p1^4
と置け、p1^4<=1000を満たす任意の素数p1について、与条件を満たす。

よって…(以下略

～～～～～～～～～～～～～～～～～～～～～～
他には、1,a,b,c,xと置いて、小さい順に大小条件を使って絞っていくのもアリです。

No.10 回答者： kony0 回答日時： 2004/01/12 21:40

この問題の解答には「知識」は必要だが、「思いつき」は必要ではないです。

必要な知識は、
ある自然数をnとして
n=(2^p1)*(3^p2)*(5^p3)*(7^p4)*・・・*(P^pk)
と素因数分解したとき、正の約数の個数が
(p1+1)(p2+1)(p3+1)(p4+1)*・・・*(pk+1)個
となることです。

これにより、約数が５個となる整数は（素数）^4の形のみであることが言える。

ちなみに約数が４個の場合は、素因数分解したときの形がab, c^3となるもの。
約数が６個の場合は、ab^2, c^5となるもの。
というような感じになります。

No.9 回答者： arukamun 回答日時： 2004/01/12 21:35

つまり、

ある自然数nの約数の個数がp個（pは素数）の場合、
n=q^(p-1)　　（qも素数）
で、約数は
1,q^1,q^2,・・・,q^(p-1)
となる。
という事ですね。

No.8 回答者： winterofmeei 回答日時： 2004/01/12 21:17

No1＆No5です

No6のliar_adanさんの

『蛇足ですが＃５さんの
＞２つ以上の別の素数を約数に持つ自然数の、約数の数は必ず偶数になります。
というのは違います。
たとえば
36 = 2^2 * 3^2
の約数の数は、(2+1)*(2+1)で9個です。
』
全然蛇足ではないです。勘違いしてました、すいません。
そして間違い指摘していただきありがとうございます。

No.7 回答者： arukamun 回答日時： 2004/01/12 21:12

プログラムを書いて見たのですが

16 = 1,2,4,8,16
81 = 1,3,9,27,81
625 = 1,5,25,125,625
の３個しか見つかりませんでした。

これを思いつくのは容易ではないですね。
ただ、５個と限定した所に意味がありそうです。
例えば４個に限定すると
1,2,3,6
という様に
６個にすれば
1,2,3,4,6,12
という様に複数の素数が混じる事があります。
なぜ、５個だと複数の素数が混じらないのか。
このあたりが不思議ですね。

No.5 回答者： winterofmeei 回答日時： 2004/01/12 20:58

『No3のfiva205cさんの回答に対して……

２１０の約数は
1, 2, 3, 5, 7, 10, 15, ……　105, 210 とたくさんあります。』

自然数nは必ず１とnという約数を持ちます。
例えば……(a,b,c…をそれぞれ別の素数として)
1)n=a*bのとき
約数は1,a,b,a*bの４つです
2)n=a*b*cのとき
約数は1,a,b,c,a*b,b*c,c*a,a*b*cの８つです
これ以上増やしても約数の数が増えていくだけなので
n=a*b*……のとき約数が５つになるnはありません

尚、２つ以上の別の素数を約数に持つ自然数の、約数の数は必ず偶数になります。

3)n=a^2のとき
約数は1,a,a^2の３つです
4)n=a^3のとき
約数は1,a,a^2,a^3の４つ
4)n=a^4のとき
約数は1,a,a^2,a^3,a^4の５つ

つまり、約数がちょうど５つある自然数はa^4（aは素数）で表されるものしかありません。