§A4.2素数と素因数分解

最終更新

素数とは、11と自分自身以外に正の約数を持たない、22以上の整数のことです。素数を小さい順に並べると、2,3,5,7,11,13,…2, 3, 5, 7, 11, 13, \dotsと続きます。11は素数に含めません。その理由は次の節で述べます。素数でない22以上の整数（4,6,8,9,…4, 6, 8, 9, \dots）は合成数と呼ばれ、必ず自分より小さい素数の積に分解できます。

1 素数と合成数

22以上の整数ppが素数であるとは、正の約数が11とppだけであることをいいます。22以上の整数で素数でないものを合成数といいます。たとえば2,3,5,7,11,132,3,5,7,11,13は素数であり、4,6,8,94,6,8,9は合成数です。整数を素数の積として表すことを素因数分解といい、その積に現れる素数を素因子といいます。

注意 1.1.11は素数に含めない。11を素数に含めると、積に因子11を任意の個数加えても値が変わらず、素数の積による表示の一意性が成り立たなくなる。

2 素因数分解の存在と一意性

素因数分解の一意性の証明には、次のユークリッドの補題を用います。

補題 2.1.ppを素数、a,ba,bを整数とする。p∣abp\mid abならば、p∣ap\mid aまたはp∣bp\mid bが成り立つ。

証明.p∤ap\nmid aとする。ppの正の約数は1,p1,pだけであるので、gcd⁡(p,a)=1\gcd(p,a)=1である。§A4.3 補題 1.1により、px+ay=1px+ay=1を満たす整数x,yx,yが存在する。両辺にbbを掛けるとpbx+aby=bpbx+aby=bとなる。p∣abp\mid abであるので左辺の各項はppで割り切れ、p∣bp\mid bが成り立つ。▨

定理 2.2.22以上の整数は、素数の積として表すことができる。この表示は、因子の順序を除いて一意である。

証明.n≥2n\ge 2とし、nnより小さい22以上の整数はすべて素数の積として表されると仮定する。nnが素数ならば、nn自身が求める表示である。nnが合成数ならば、n=abn=abを満たす整数a,ba,bを2≤a,b<n2\le a,b<nとなるように取ることができる。帰納法の仮定によりa,ba,bはともに素数の積として表されるので、nnも同じ形で表される。n=2n=2の場合は素数の場合に含まれるので、帰納法によって存在が従う。

n=p1⋯pr=q1⋯qsn=p_1\cdots p_r=q_1\cdots q_sを二つの素数の積による表示とし、r,s≥1r,s\ge1とする。補題 2.1を繰り返し用いると、p1p_1はいずれかのqjq_jを割り切る。qjq_jは素数でありp1>1p_1>1であるので、p1=qjp_1=q_jである。因子の順序を入れ替え、両辺からこの共通因子を一つずつ除く。残った積にも同じ議論を繰り返すことができる。一方の因子だけが先に尽きると、11が素数の空でない積に等しくなるが、そのような積は22以上である。したがって両辺の因子は同時に尽き、二つの表示は順序を除いて一致する。▨

定理 2.2を算術の基本定理といいます。

例 2.3.60=22×3×560=2^2\times3\times5である。算術の基本定理により、6060の素数の積による表示には、22が二つ、33と55が一つずつ現れる。

3 エラトステネスの篩

整数N≥2N\ge2に対し、NN以下の素数を列挙する方法を、エラトステネスの篩といいます。

  1. 22からNNまでの整数を並べます。
  2. まだ消しておらず素数として確定していない最小の数をppとします。p2>Np^2>Nなら終了します。p2≤Np^2\le Nならppを素数として確定し、ppの倍数のうちpp自身を除く数をすべて消します。
  3. 未確定の数が残っていれば項目 (2)を繰り返し、残っていなければ終了します。

終了時に消されずに残った数が、NN以下の素数です。定理 2.2により、合成数m≤Nm\le Nの最小の素因子qqについてm=qkm=qk、k≥qk\ge qと書くことができるので、q2≤m≤Nq^2\le m\le Nです。したがって、N\sqrt{N}以下の素数の倍数を消せば、NN以下の合成数はすべて消されます。そのため、p2>Np^2>Nとなった時点で手順を終了してよいことになります。

4 約数の個数と総和

命題 4.1.k≥1k\ge1とし、相異なる素数p1,…,pkp_1,\ldots,p_kと正の整数e1,…,eke_1,\ldots,e_kによって、N=p1e1⋯pkekN=p_1^{e_1}\cdots p_k^{e_k}と表されているとする。NNの正の約数は、0≤fi≤ei0\le f_i\le e_iを満たす整数fif_iを用いてp1f1⋯pkfkp_1^{f_1}\cdots p_k^{f_k}と一意に表される。正の約数の個数と総和は、それぞれ

∏i=1k(ei+1),∏i=1k(1+pi+⋯+piei)\prod_{i=1}^k(e_i+1),\qquad \prod_{i=1}^k(1+p_i+\cdots+p_i^{e_i})

である。

証明.ddがNNの正の約数なら、正の整数mmを用いてN=dmN=dmと書くことができる。定理 2.2により、ddに現れる素数はpip_iのいずれかであり、その指数はeie_iを超えない。逆に0≤fi≤ei0\le f_i\le e_iなら、p1e1−f1⋯pkek−fkp_1^{e_1-f_1}\cdots p_k^{e_k-f_k}を掛けるとNNになるので、p1f1⋯pkfkp_1^{f_1}\cdots p_k^{f_k}はNNの約数である。指数の異なる組から同じ約数が得られることは、素因数分解の一意性によって起こらない。各fif_iにはei+1e_i+1通りの選び方があるので、約数の個数は選び方の個数の積である。総和の式の積を分配法則で展開すると、各因子からpifip_i^{f_i}を一つずつ選んだ積が一度ずつ現れる。各項は正の約数と一対一に対応するので、この展開の値が約数の総和である。▨

例 4.2.360=23×32×5360=2^3\times3^2\times5なので、正の約数の個数は(3+1)(2+1)(1+1)=24(3+1)(2+1)(1+1)=24、総和は(1+2+4+8)(1+3+9)(1+5)=15×13×6=1170(1+2+4+8)(1+3+9)(1+5)=15\times13\times6=1170である。11の正の約数は11だけなので、約数の個数と総和はいずれも11である。

5 最大公約数と最小公倍数

二つの正の整数に共通する正の倍数のうち、最小のものを最小公倍数と呼びます。

命題 5.1.A,BA,Bを正の整数とする。p1,…,pkp_1,\ldots,p_kをAAまたはBBの素因子を重複なく並べたものとし、00以上の整数ai,bia_i,b_iを用いてA=∏i=1kpiaiA=\prod_{i=1}^k p_i^{a_i}、B=∏i=1kpibiB=\prod_{i=1}^k p_i^{b_i}と表す。現れない素数の指数は00とする。A=B=1A=B=1のときはk=0k=0とし、因子のない積は11とする。最大公約数ddと最小公倍数LLは

d=∏i=1kpimin⁡(ai,bi),L=∏i=1kpimax⁡(ai,bi)d=\prod_{i=1}^k p_i^{\min(a_i,b_i)},\qquad L=\prod_{i=1}^k p_i^{\max(a_i,b_i)}

であり、dL=ABdL=ABが成り立つ。

証明.A,BA,Bの一方が11なら、最大公約数は11、最小公倍数は他方の数であり、表示された式が成り立つ。A,B≥2A,B\ge2とする。命題 4.1により、公約数に現れるpip_iの指数はai,bia_i,b_iの両方以下である。したがって、すべての正の公約数は表示されたddを割り切り、dd自身も公約数である。よってddは最大公約数である。定理 2.2により、正の公倍数には各pip_iが少なくともmax⁡(ai,bi)\max(a_i,b_i)個現れる。したがって、すべての正の公倍数は表示されたLLの倍数であり、LL自身も公倍数なので最小である。min⁡(ai,bi)+max⁡(ai,bi)=ai+bi\min(a_i,b_i)+\max(a_i,b_i)=a_i+b_iであるので、dL=ABdL=ABが成り立つ。▨

問題 5.2. 最大公約数が1212、最小公倍数が180180である正の整数の組(A,B)(A,B)を、A≤BA\le Bのもとですべて求めよ。

解答.

A=12uA=12u、B=12vB=12vと書くと、u,vu,vは正の整数であり、u≤vu\le vである。u,vu,vに11より大きい公約数hhがあれば、12h12hがA,BA,Bの公約数となるので、gcd⁡(u,v)=1\gcd(u,v)=1である。命題 5.1によりAB=12×180AB=12\times180なので、uv=15uv=15となる。u≤vu\le vを満たす正の因数の組は(1,15)(1,15)と(3,5)(3,5)だけで、いずれも互いに素である。したがって候補は(12,180)(12,180)と(36,60)(36,60)である。素因数分解から両方の組の最大公約数は1212であり、積は12×18012\times180なので、同じ命題により最小公倍数は180180である。よって求める組は(12,180)(12,180)と(36,60)(36,60)で尽くされる。▨

6 素数の無限性

定理 6.1. 素数は無限に存在する。

証明. 素数が有限個しかないと仮定し、すべての素数をp1,p2,…,pnp_1,p_2,\ldots,p_nとする。22は素数であるのでn≥1n\ge1である。N=p1p2⋯pn+1N=p_1p_2\cdots p_n+1とおく。NNは各pip_iで割ると11余るので、どのpip_iによっても割り切れない。一方、N≥2N\ge2であるので、定理 2.2によりNNの素因子qqが存在する。qqは素数であるのに、列挙したどのpip_iとも異なる。これはp1,…,pnp_1,\ldots,p_nがすべての素数であるという仮定に矛盾する。したがって素数は無限に存在する。▨

例 6.2. 素数の積に11を加えた数が素数になるとは限らない。たとえば、

2×3×5×7×11×13+1=30031=59×5092\times3\times5\times7\times11\times13+1=30031=59\times509

は合成数である。

閑話休題：連続する合成数と双子素数 任意の整数N≥2N\ge2に対して、N!=1×2×⋯×NN!=1\times2\times\cdots\times Nとおきます。N!+2, N!+3, …, N!+NN!+2,\ N!+3,\ \ldots,\ N!+NはN−1N-1個の連続した合成数です。実際、2≤k≤N2\le k\le Nなら、N!+kN!+kはkkで割り切れ、N!+k>k>1N!+k>k>1であるので、N!+kN!+kは合成数です。NNを大きく取ることにより、連続した合成数の列を任意の長さにすることができます。

(3,5),(11,13),(41,43)(3,5),(11,13),(41,43)のように差が22の素数の組を双子素数と呼びます。双子素数が無限に存在するかという問題は、百年以上未解決です。 2013年に張益唐（チャン・イタン）は、差が70007000万以下の素数の組が無限に存在することを証明しました。その後、数学者たちの共同オンライン作業であるポリマス・プロジェクトによって、差の上限は縮められました。差が246246以下の素数の組が無限に存在するという結果も得られています。差がちょうど22の双子素数が無限に存在するという予想は、依然として未解決です。

7 例題

レベル1 — 約数の個数と総和

次の問いに答えよ。d(n) は n の正の約数の個数、σ(n)\sigma(n)は n の正の約数の総和を表す。

解法の型n==p1e1p1^e1…pkekpk^ekに対し d(n)==Π(ei+1)、σ(n)\sigma(n)==Π (p^(e+1)−1)/(p−1)（素因数分解の一意性から従う）

例 7.1. 441 の正の約数の個数 d(441) を求めよ。

n=32⋅72=441,d(n)=?n = 3^{2} \cdot 7^{2} = 441, \qquad d(n) = ?

答99

注意 約数は各素因数 p の指数を 0 から e まで独立に選んで得られるので、d(n)==Π(eᵢ+1)==(2+1)(2+1)==9。素因数分解の一意性（算術の基本定理）が、この数え上げに重複も漏れもないことを保証している。

例 7.2. 7605 の正の約数の個数 d(7605) を求めよ。

n=32⋅5⋅132=7605,d(n)=?n = 3^{2} \cdot 5 \cdot 13^{2} = 7605, \qquad d(n) = ?

答1818

注意 約数は各素因数 p の指数を 0 から e まで独立に選んで得られるので、d(n)==Π(eᵢ+1)==(2+1)(1+1)(2+1)==18。素因数分解の一意性（算術の基本定理）が、この数え上げに重複も漏れもないことを保証している。

例 7.3. 275 の正の約数の総和σ(275)\sigma(275)を求めよ。

n=52⋅11=275,σ(n)=?n = 5^{2} \cdot 11 = 275, \qquad \sigma(n) = ?

答372372

注意 各素因数について等比数列の和 1 + p + … +pe=p^e =(p^(e+1)−1)/(p−1) を作り、掛け合わせる:σ(n)=\sigma(n) =(5³−1)/(5−1) × (11²−1)/(11−1)==31 × 12==372。展開すると n のすべての約数がちょうど1回ずつ現れる（これも素因数分解の一意性による）。

例 7.4. 1911 の正の約数の総和σ(1911)\sigma(1911)を求めよ。

n=3⋅72⋅13=1911,σ(n)=?n = 3 \cdot 7^{2} \cdot 13 = 1911, \qquad \sigma(n) = ?

答31923192

注意 各素因数について等比数列の和 1 + p + … +pe=p^e =(p^(e+1)−1)/(p−1) を作り、掛け合わせる:σ(n)=\sigma(n) =(3²−1)/(3−1) × (7³−1)/(7−1) × (13²−1)/(13−1)==4 × 57 × 14==3192。展開すると n のすべての約数がちょうど1回ずつ現れる（これも素因数分解の一意性による）。

例 7.5. 3773 の正の約数の総和σ(3773)\sigma(3773)を求めよ。

n=73⋅11=3773,σ(n)=?n = 7^{3} \cdot 11 = 3773, \qquad \sigma(n) = ?

答48004800

注意 各素因数について等比数列の和 1 + p + … +pe=p^e =(p^(e+1)−1)/(p−1) を作り、掛け合わせる:σ(n)=(74−1)/(7−1)\sigma(n) = (7^{4}-1)/(7-1)× (11²−1)/(11−1)==400 × 12==4800。展開すると n のすべての約数がちょうど1回ずつ現れる（これも素因数分解の一意性による）。

例 7.6. 1715 の正の約数の総和σ(1715)\sigma(1715)を求めよ。

n=5⋅73=1715,σ(n)=?n = 5 \cdot 7^{3} = 1715, \qquad \sigma(n) = ?

答24002400

注意 各素因数について等比数列の和 1 + p + … +pe=p^e =(p^(e+1)−1)/(p−1) を作り、掛け合わせる:σ(n)=\sigma(n) =(5²−1)/(5−1) ×(74−1)/(7−1)=(7^{4}-1)/(7-1) =6 × 400==2400。展開すると n のすべての約数がちょうど1回ずつ現れる（これも素因数分解の一意性による）。

例 7.7. 40 が完全数（自分自身を除く正の約数の総和が自分自身に等しい数）であるかどうか判定せよ。

n=40は完全数か？n = 40 \quad \text{は完全数か？}

答σ(40)=90≠80=2⋅40⇒\sigma(40) = 90 \ne 80 = 2 \cdot 40 \quad \Rightarrow完全数でない

注意 40==2³×5 なのでσ(40)=(24−1)/(2−1)\sigma(40) = (2^{4}-1)/(2-1)× (5²−1)/(5−1)==15 × 6==90。完全数とは「自分自身を除く約数の和が n」、すなわちσ(n)=\sigma(n) =2n のこと。σ(40)\sigma(40)− 40==50 で 40 と一致しないので完全数ではない（過剰数）。

例 7.8. 585 の正の約数の総和σ(585)\sigma(585)を求めよ。

n=32⋅5⋅13=585,σ(n)=?n = 3^{2} \cdot 5 \cdot 13 = 585, \qquad \sigma(n) = ?

答10921092

注意 各素因数について等比数列の和 1 + p + … +pe=p^e =(p^(e+1)−1)/(p−1) を作り、掛け合わせる:σ(n)=\sigma(n) =(3³−1)/(3−1) × (5²−1)/(5−1) × (13²−1)/(13−1)==13 × 6 × 14==1092。展開すると n のすべての約数がちょうど1回ずつ現れる（これも素因数分解の一意性による）。

例 7.9. 28 が完全数（自分自身を除く正の約数の総和が自分自身に等しい数）であるかどうか判定せよ。

n=28は完全数か？n = 28 \quad \text{は完全数か？}

答σ(28)=56=2⋅28⇒\sigma(28) = 56 = 2 \cdot 28 \quad \Rightarrow完全数である

注意 28==2²×7 なのでσ(28)=\sigma(28) =(2³−1)/(2−1) × (7²−1)/(7−1)==7 × 8==56。完全数とは「自分自身を除く約数の和が n」、すなわちσ(n)=\sigma(n) =2n のこと。σ(28)=\sigma(28) =56==2×28 なので 28 は完全数（6, 28, 496, 8128 と続く）。

例 7.10. 4394 の正の約数の個数 d(4394) を求めよ。

n=2⋅133=4394,d(n)=?n = 2 \cdot 13^{3} = 4394, \qquad d(n) = ?

答88

注意 約数は各素因数 p の指数を 0 から e まで独立に選んで得られるので、d(n)==Π(eᵢ+1)==(1+1)(3+1)==8。素因数分解の一意性（算術の基本定理）が、この数え上げに重複も漏れもないことを保証している。

8 演習

レベル1 — 約数の個数と総和

次の問いに答えよ。d(n) は n の正の約数の個数、σ(n)\sigma(n)は n の正の約数の総和を表す。

解法の型n==p1e1p1^e1…pkekpk^ekに対し d(n)==Π(ei+1)、σ(n)\sigma(n)==Π (p^(e+1)−1)/(p−1)（素因数分解の一意性から従う）

問題 8.1. 6 が完全数（自分自身を除く正の約数の総和が自分自身に等しい数）であるかどうか判定せよ。

n=6は完全数か？n = 6 \quad \text{は完全数か？}
解答.

答σ(6)=12=2⋅6⇒\sigma(6) = 12 = 2 \cdot 6 \quad \Rightarrow完全数である

注意 6==2×3 なのでσ(6)=\sigma(6) =(2²−1)/(2−1) × (3²−1)/(3−1)==3 × 4==12。完全数とは「自分自身を除く約数の和が n」、すなわちσ(n)=\sigma(n) =2n のこと。σ(6)=\sigma(6) =12==2×6 なので 6 は完全数（6, 28, 496, 8128 と続く）。▨

問題 8.2. 3087 の正の約数の総和σ(3087)\sigma(3087)を求めよ。

n=32⋅73=3087,σ(n)=?n = 3^{2} \cdot 7^{3} = 3087, \qquad \sigma(n) = ?
解答.

答52005200

注意 各素因数について等比数列の和 1 + p + … +pe=p^e =(p^(e+1)−1)/(p−1) を作り、掛け合わせる:σ(n)=\sigma(n) =(3³−1)/(3−1) ×(74−1)/(7−1)=(7^{4}-1)/(7-1) =13 × 400==5200。展開すると n のすべての約数がちょうど1回ずつ現れる（これも素因数分解の一意性による）。▨

問題 8.3. 338 の正の約数の個数 d(338) を求めよ。

n=2⋅132=338,d(n)=?n = 2 \cdot 13^{2} = 338, \qquad d(n) = ?
解答.

答66

注意 約数は各素因数 p の指数を 0 から e まで独立に選んで得られるので、d(n)==Π(eᵢ+1)==(1+1)(2+1)==6。素因数分解の一意性（算術の基本定理）が、この数え上げに重複も漏れもないことを保証している。▨

問題 8.4. 496 が完全数（自分自身を除く正の約数の総和が自分自身に等しい数）であるかどうか判定せよ。

n=496は完全数か？n = 496 \quad \text{は完全数か？}
解答.

答σ(496)=992=2⋅496⇒\sigma(496) = 992 = 2 \cdot 496 \quad \Rightarrow完全数である

注意 496=24×31= 2^{4}\times31なのでσ(496)=(25−1)/(2−1)\sigma(496) = (2^{5}-1)/(2-1)× (31²−1)/(31−1)==31 × 32==992。完全数とは「自分自身を除く約数の和が n」、すなわちσ(n)=\sigma(n) =2n のこと。σ(496)=\sigma(496) =992==2×496 なので 496 は完全数（6, 28, 496, 8128 と続く）。▨

問題 8.5. 325 の正の約数の総和σ(325)\sigma(325)を求めよ。

n=52⋅13=325,σ(n)=?n = 5^{2} \cdot 13 = 325, \qquad \sigma(n) = ?
解答.

答434434

注意 各素因数について等比数列の和 1 + p + … +pe=p^e =(p^(e+1)−1)/(p−1) を作り、掛け合わせる:σ(n)=\sigma(n) =(5³−1)/(5−1) × (13²−1)/(13−1)==31 × 14==434。展開すると n のすべての約数がちょうど1回ずつ現れる（これも素因数分解の一意性による）。▨

問題 8.6. 30 が完全数（自分自身を除く正の約数の総和が自分自身に等しい数）であるかどうか判定せよ。

n=30は完全数か？n = 30 \quad \text{は完全数か？}
解答.

答σ(30)=72≠60=2⋅30⇒\sigma(30) = 72 \ne 60 = 2 \cdot 30 \quad \Rightarrow完全数でない

注意 30==2×3×5 なのでσ(30)=\sigma(30) =(2²−1)/(2−1) × (3²−1)/(3−1) × (5²−1)/(5−1)==3 × 4 × 6==72。完全数とは「自分自身を除く約数の和が n」、すなわちσ(n)=\sigma(n) =2n のこと。σ(30)\sigma(30)− 30==42 で 30 と一致しないので完全数ではない（過剰数）。▨

問題 8.7. 28 が完全数（自分自身を除く正の約数の総和が自分自身に等しい数）であるかどうか判定せよ。

n=28は完全数か？n = 28 \quad \text{は完全数か？}
解答.

答σ(28)=56=2⋅28⇒\sigma(28) = 56 = 2 \cdot 28 \quad \Rightarrow完全数である

注意 28==2²×7 なのでσ(28)=\sigma(28) =(2³−1)/(2−1) × (7²−1)/(7−1)==7 × 8==56。完全数とは「自分自身を除く約数の和が n」、すなわちσ(n)=\sigma(n) =2n のこと。σ(28)=\sigma(28) =56==2×28 なので 28 は完全数（6, 28, 496, 8128 と続く）。▨

問題 8.8. 12 が完全数（自分自身を除く正の約数の総和が自分自身に等しい数）であるかどうか判定せよ。

n=12は完全数か？n = 12 \quad \text{は完全数か？}
解答.

答σ(12)=28≠24=2⋅12⇒\sigma(12) = 28 \ne 24 = 2 \cdot 12 \quad \Rightarrow完全数でない

注意 12==2²×3 なのでσ(12)=\sigma(12) =(2³−1)/(2−1) × (3²−1)/(3−1)==7 × 4==28。完全数とは「自分自身を除く約数の和が n」、すなわちσ(n)=\sigma(n) =2n のこと。σ(12)\sigma(12)− 12==16 で 12 と一致しないので完全数ではない（過剰数）。▨

問題 8.9. 400 の正の約数の総和σ(400)\sigma(400)を求めよ。

n=24⋅52=400,σ(n)=?n = 2^{4} \cdot 5^{2} = 400, \qquad \sigma(n) = ?
解答.

答961961

注意 各素因数について等比数列の和 1 + p + … +pe=p^e =(p^(e+1)−1)/(p−1) を作り、掛け合わせる:σ(n)=(25−1)/(2−1)\sigma(n) = (2^{5}-1)/(2-1)× (5³−1)/(5−1)==31 × 31==961。展開すると n のすべての約数がちょうど1回ずつ現れる（これも素因数分解の一意性による）。▨

問題 8.10. 24 が完全数（自分自身を除く正の約数の総和が自分自身に等しい数）であるかどうか判定せよ。

n=24は完全数か？n = 24 \quad \text{は完全数か？}
解答.

答σ(24)=60≠48=2⋅24⇒\sigma(24) = 60 \ne 48 = 2 \cdot 24 \quad \Rightarrow完全数でない

注意 24==2³×3 なのでσ(24)=(24−1)/(2−1)\sigma(24) = (2^{4}-1)/(2-1)× (3²−1)/(3−1)==15 × 4==60。完全数とは「自分自身を除く約数の和が n」、すなわちσ(n)=\sigma(n) =2n のこと。σ(24)\sigma(24)− 24==36 で 24 と一致しないので完全数ではない（過剰数）。▨

問題 8.11. 40 が完全数（自分自身を除く正の約数の総和が自分自身に等しい数）であるかどうか判定せよ。

n=40は完全数か？n = 40 \quad \text{は完全数か？}
解答.

答σ(40)=90≠80=2⋅40⇒\sigma(40) = 90 \ne 80 = 2 \cdot 40 \quad \Rightarrow完全数でない

注意 40==2³×5 なのでσ(40)=(24−1)/(2−1)\sigma(40) = (2^{4}-1)/(2-1)× (5²−1)/(5−1)==15 × 6==90。完全数とは「自分自身を除く約数の和が n」、すなわちσ(n)=\sigma(n) =2n のこと。σ(40)\sigma(40)− 40==50 で 40 と一致しないので完全数ではない（過剰数）。▨

問題 8.12. 297 の正の約数の個数 d(297) を求めよ。

n=33⋅11=297,d(n)=?n = 3^{3} \cdot 11 = 297, \qquad d(n) = ?
解答.

答88

注意 約数は各素因数 p の指数を 0 から e まで独立に選んで得られるので、d(n)==Π(eᵢ+1)==(3+1)(1+1)==8。素因数分解の一意性（算術の基本定理）が、この数え上げに重複も漏れもないことを保証している。▨

問題 8.13. 2160 の正の約数の総和σ(2160)\sigma(2160)を求めよ。

n=24⋅33⋅5=2160,σ(n)=?n = 2^{4} \cdot 3^{3} \cdot 5 = 2160, \qquad \sigma(n) = ?
解答.

答74407440

注意 各素因数について等比数列の和 1 + p + … +pe=p^e =(p^(e+1)−1)/(p−1) を作り、掛け合わせる:σ(n)=(25−1)/(2−1)\sigma(n) = (2^{5}-1)/(2-1)×(34−1)/(3−1)(3^{4}-1)/(3-1)× (5²−1)/(5−1)==31 × 40 × 6==7440。展開すると n のすべての約数がちょうど1回ずつ現れる（これも素因数分解の一意性による）。▨

問題 8.14. 1183 の正の約数の個数 d(1183) を求めよ。

n=7⋅132=1183,d(n)=?n = 7 \cdot 13^{2} = 1183, \qquad d(n) = ?
解答.

答66

注意 約数は各素因数 p の指数を 0 から e まで独立に選んで得られるので、d(n)==Π(eᵢ+1)==(1+1)(2+1)==6。素因数分解の一意性（算術の基本定理）が、この数え上げに重複も漏れもないことを保証している。▨

問題 8.15. 1936 の正の約数の個数 d(1936) を求めよ。

n=24⋅112=1936,d(n)=?n = 2^{4} \cdot 11^{2} = 1936, \qquad d(n) = ?
解答.

答1515

注意 約数は各素因数 p の指数を 0 から e まで独立に選んで得られるので、d(n)==Π(eᵢ+1)==(4+1)(2+1)==15。素因数分解の一意性（算術の基本定理）が、この数え上げに重複も漏れもないことを保証している。▨

前提記事