大学入試数学 約数個数からの逆算—素数の指数の組を絞って元の整数を復元する｜武蔵野個別指導塾

約数の個数を指数に1を加えた数の積に直し、素因数の種類数と重複を見ながら整数を復元する道筋をたどる約数個数からの逆算。

よくあるのは、高校生が演習の解き直しで、素数の指数を入れ替えてできる数を二度数える場面です。指数の並びが違っても、同じ素数に同じ指数が付いていれば元の整数は同じです。一方、異なる素数に異なる指数を付け替えれば、普通は別の整数になります。何を固定し、何を並べ替えたかを確かめながら、約数の個数から整数の形を逆算しましょう。

個数だけで整数が決まるでしょうか

正整数の約数の個数を指定される問題には、整数の形をすべて表す型、ある範囲内の整数を列挙する型、最小の整数を求める型があります。いずれも最初に見る条件は、約数の個数だけでなく、異なる素因数が何種類あるかです。素因数の種類数が決まれば、個数を何個の因子に分けるかが決まります。

ただし、約数の個数と種類数だけでは、一般には整数そのものは1つに決まりません。素数を変えても指数が同じなら個数は変わらないからです。範囲や最小という条件があるときは、その条件を後で使います。まず指数の候補を尽くし、次に素数の候補を調べ、最後に元の条件に戻すという順序が有効です。

積の分け方が指数にどう対応するか

1より大きい正整数 N の異なる素因数を p、q、… とし、それぞれの指数を正整数 a、b、… とします。例えば N = pᵃqᵇ なら、正の約数は p の指数を 0 から a、q の指数を 0 から b まで独立に選んで作れます。選択肢はそれぞれ a + 1 個、b + 1 個なので、正の約数の個数は (a + 1)(b + 1) です。指数を0にする選択があるため、1も約数に含まれます。

逆向きには、指定された個数を2以上の整数の積に分け、各因子から1を引きます。因子が1なら指数は0であり、その素数は素因数として現れません。したがって種類数を数える際に1を因子として混ぜてはいけません。素因数がちょうど2種類なら、2以上の因子をちょうど2個使います。

図1のように、たとえば個数が12で種類数が2なら、順序を除いた因子の組は (2, 6)、(3, 4) です。それぞれ指数の組 (1, 5)、(2, 3) に対応します。12 = 1・12 は指数0を含むので、2種類の条件には合いません。積の分け方を列挙するときは、小さい因子から順に調べ、積が12に戻ることも確かめます。

図1では因子の組の順序を固定しています。実際の素数が p < q と固定された後は、異なる指数を p と q にどう割り当てるかを別に調べます。因子の組を順不同で列挙することと、指数の割当てを省くことは別です。同じ指数の入替えは同じ数ですが、異なる指数の入替えは異なる数です。素因数分解の一意性によって、この区別を正確にできます。

基本例題：指定した2つの素数に戻す

標準。正整数 N の異なる素因数は 2 と 5 のみで、正の約数は12個あります。条件を満たすすべての N を整数で求めてください。

N = 2ᵃ5ᵇ とおくと、a、b は正整数です。約数の個数の条件は次の通りです。

(a + 1)(b + 1) = 12
(a + 1, b + 1) = (2, 6), (6, 2), (3, 4), (4, 3)
(a, b) = (1, 5), (5, 1), (2, 3), (3, 2)

したがって、図2のように、指数を素数に割り当てて計算します。

2¹5⁵ = 6250
2⁵5¹ = 160
2²5³ = 500
2³5² = 200

答えは 160、200、500、6250 です。図2の4行では各整数の素因数が2と5で、指数に1を加えた数の積は順に 6・2、4・3、3・4、2・6 です。いずれも12なので元の条件を満たします。逆に、正の指数から作った2以上の因子の組は上の4通りに限られるため、ほかの答えはありません。

ここで、指数の組を (1, 5)、(2, 3) の2通りだけとするのは不十分です。小さい指数を小さい素数に付けるという条件は問題にないためです。逆に、2と5の順序を改めて入れ替えた式を同じ指数の割当てとして数えると、同じ整数を重ねます。素数の順序を先に固定すると見通しが立ちます。

標準から発展へ：範囲と最小を使う

例題2

やや難。正整数 N は異なる素因数をちょうど2種類もち、正の約数が8個あります。N が100以下のとき、条件を満たす N をすべて整数で求めてください。

N = pᵃqᵇ、p < q とおきます。p、q は素数、a、b は正整数です。2以上の2因子に8を分ける方法は 2・4 だけです。よって指数は1と3であり、次のどちらかです。

N = p³q
N = pq³

まず N = p³q を調べます。p < q より q は p より大きい素数です。p が3以上なら p³q は少なくとも 3³・5 = 135 なので100を超えます。よって p = 2 です。

8q ≤ 100
q ≤ 12
q = 3, 5, 7, 11
N = 24, 40, 56, 88

次に N = pq³ です。q が5以上なら p ≥ 2 ですから pq³ ≥ 2・5³ = 250 となります。したがって q = 3、p = 2 です。

N = 2・3³
N = 54

答えは 24、40、54、56、88 です。それぞれ異なる2素数の指数が3と1であり、約数は4・2 = 8個です。また最大の88まで100以下です。上限を示してから素数を列挙したので、試す範囲を途中で打ち切ってはいません。

別の見方では、大きい指数を付ける素数を r、小さい指数を付ける素数を s として r³s ≤ 100 を調べられます。ただし r と s の大小は決まらないため、r = 2 の場合だけで終えず r = 3 も調べます。どちらの方法でも、指数の役割と素数の大小を混同しないことが必要です。

例題3

難。異なる素因数をちょうど3種類もち、正の約数が24個ある正整数のうち、最小のものを整数で求めてください。

指数に1を加えた3個の整数は2以上で、積は24です。小さい順に並べれば、その組は次の2通りです。

24 = 2・2・6
24 = 2・3・4
指数の組は (1, 1, 5), (1, 2, 3)

この列挙が尽きる理由を見ます。最小因子が3以上なら積は少なくとも 3・3・3 = 27 です。したがって最小因子は2で、残り2因子の積は12です。2以上で小さい順の組は (2, 6)、(3, 4) に限られます。

最小にするには素数は2、3、5を使います。どの3種類の素数を小さい順に並べても、それぞれ2、3、5以上なので、同じ正の指数を対応させた積は小さくなりません。また、小さい素数に大きい指数を付けると積は大きくなりません。実際、p < q、a > b なら次の関係があります。

pᵃqᵇ = pᵇqᵇ・p の (a - b) 乗
pᵇqᵃ = pᵇqᵇ・q の (a - b) 乗
pᵃqᵇ < pᵇqᵃ

よって各指数の組の最小値を比較します。

2⁵・3・5 = 480
2³・3²・5 = 360
360 < 480

答えは360です。360 = 2³・3²・5 なので素因数は3種類、約数は 4・3・2 = 24個です。候補が条件を満たすことと、どの候補も360未満にならないことの両方を示しました。単に小さい素数を試して360を見つけるだけでは、最小である理由は残ります。

なお、大きい指数を小さい素数に付ける原則は、積を最小にする条件で使いました。素数ごとの指数が指定された問題や、範囲内のすべての数を求める問題では、交換した場合も調べなければなりません。最小化のための比較を、列挙全体の規則に変えてはいけません。

誤答を直す：同じ数を何回数えたか

基本例題で「2¹5⁵ と 5⁵2¹ は指数の並びが違うので2個」と数えたとします。これは積の順序を変えただけで、どちらも6250です。一方、2⁵5¹ は160であり、こちらは2と5に付く指数が入れ替わった別の数です。

図3のように、素数を小さい順に固定して指数を書き直すと、同じ数かどうかを判定できます。2¹5⁵ と 5⁵2¹ はどちらも (2の指数, 5の指数) = (1, 5) です。2⁵5¹ は (5, 1) なので区別します。

図3の修正は、素数と指数の対応を保存する操作です。順番だけを整える際に指数を素数から外して並べ替えると、別の整数に変わってしまいます。また、指数が等しい場合は、指数の交換自体が同じ割当てです。たとえば p²q² で2つの指数を交換しても新しい数は生じません。

個数の分解ができない場合もあります。素因数が2種類なら2以上の因子を2個必要とします。指定個数が素数なら、そのような分解はなく、条件を満たす整数は存在しません。因子1を無理に使うと、存在しない2種類目を数えたことになります。候補がないという結論も、分解の条件を示してから書きます。

練習問題

いずれも正の約数を数えます。求める整数はすべて正整数です。

1. 標準。素因数が3と7のみで、約数が6個ある整数をすべて整数で求めてください。
2. 標準。素因数がちょうど2種類で、約数が5個ある整数が存在するか判定し、理由を示してください。
3. やや難。素因数がちょうど2種類で、約数が6個ある50以下の整数をすべて整数で求めてください。
4. やや難。素因数がちょうど3種類で、約数が18個ある整数の最小値を整数で求めてください。
5. 難。素因数が2と3のみで、約数が15個ある整数をすべて整数で求めてください。

練習問題の答えと道筋

1. 指数を a、b とすると (a + 1)(b + 1) = 6 で、両因子は2以上です。順序を含め (2, 3)、(3, 2) なので指数は (1, 2)、(2, 1) です。

3・7² = 147
3²・7 = 63

答えは63、147です。どちらも素因数は3と7で、約数は 3・2 = 6個です。

2. 存在しません。5は素数なので、2以上の2整数の積として表せません。指数に1を加えた数がそのような積を作る必要があるため、条件に矛盾します。1・5 は一方の指数が0になり、素因数が1種類です。

3. 指数は1と2です。p < q とすると N = p²q または pq² です。前者で p ≥ 3 なら N ≥ 3²・5 = 45、さらに p ≥ 5 なら N ≥ 5²・7 > 50 です。p = 2 では q ≤ 12 より q = 3、5、7、11、p = 3 では q = 5 です。後者は q ≥ 5 なら N ≥ 2・5² = 50 で、等号を含め q = 5、p = 2 が可能です。q ≥ 7 なら N > 50、q = 3 なら p = 2 です。

p²q: 12, 20, 28, 44, 45
pq²: 18, 50

答えは12、18、20、28、44、45、50です。各数は異なる2素数の指数が2と1で、約数は3・2 = 6個です。すべて50以下です。

4. 18を2以上の3因子に分けると 2・3・3 だけです。指数は1、2、2で、最小の素数から大きい指数を付けます。

2²・3²・5 = 180

答えは180です。180 = 2²・3²・5 で、素因数は3種類、約数は3・3・2 = 18個です。素数を大きくするか、指数1をより小さい素数に付けると積は小さくならないので、これが最小です。

5. 15を2以上の2因子に分けると 3・5 です。指数は2と4で、それぞれの割当てを調べます。

2²・3⁴ = 324
2⁴・3² = 144

答えは144、324です。各整数の素因数は2と3で、約数は5・3 = 15個です。指数の交換は2通りとも異なる整数を作り、ほかの因子の組はありません。

手元に残す要点

• 約数の個数を、指数に1を加えた2以上の因子の積に直します。
• 因子の個数は異なる素因数の種類数と一致します。
• 素数の順序を固定し、異なる指数の割当てを尽くします。
• 最小値には素数の大小と指数の交換を比較します。
• 得た整数を元の種類数と約数個数に戻して確かめます。

どこでつまずいたかを見分ける

候補が足りないときは、因子の積の分解が漏れたのか、分解後の指数の割当てが漏れたのかを分けて見ます。候補が多すぎるときは、素数を小さい順に固定して各指数を記録し、同じ組が重なっていないかを確認します。個別指導で確かめるなら、候補を1つ選び、その素因数分解から約数の個数へ戻る式を書いてもらうと、逆算のどの段階がずれたか見えます。因子の分解と素数への割当てを区別すれば、約数個数からの逆算は漏れなくたどれます。