このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ
*目次 [#s11091ab]

#contents


*完全数 [#u5c6c976]

[定義]自然数nに対して、n自身を除くすべての正の約数の和がnと一致するとき、nを''完全数''という。

[定義]自然数nの正の約数すべての和をσ(n)と書く。

[定理]自然数nが完全数であるとき、σ(n)=2nが成り立つ。

例:n=6は完全数である。なぜならば、6の正の約数は1,2,3,6であり、6自身を除いた数を足すと、1+2+3=6となるからである。

-(左辺)=σ(6)=1+2+3+6=(1+2+3)+6=6+6=12
-(右辺)=2・6=12

*オイラー関数と完全数 [#o3097727]

**素因数分解がわかっている自然数に対するσ(n)の計算 [#q2ec15b9]

[定理]自然数nの素因数分解をn=pSUP{a};qSUP{b};rSUP{c};…とすれば、σ(n)は次の式で計算できる。~
&mimetex("\sigma(n)=\frac{p^{a+1} - 1}{p-1} \cdot \frac{q^{b+1} - 1}{q-1} \cdot\frac{r^{c+1} - 1}{r-1} \cdots");

[証明]次に示す等比級数の積を考える。

(1+p+…+pSUP{a};)(1+q+…+qSUP{b};)(1+r+…+rSUP{c};)…

 これを展開した際に現れる各項pSUP{α};qSUP{β};rSUP{γ};…により、nの正の約数が(重複なく)すべて与えられる。~
 なぜならば、[定理]「合成数nの素因数分解をn=pSUP{a};qSUP{b};rSUP{c};…とすれば、その正の約数の全体はpSUP{α};qSUP{β};rSUP{γ};…、0≦α≦a、0≦β≦b、0≦γ≦c、…で与えられる」が成り立つから。

 よって、この積の値はσ(n)に等しい。

σ(n)=(1+p+…+pSUP{a};)(1+q+…+qSUP{b};)(1+r+…+rSUP{c};)…

 さらに、等比級数の公式

&mimetex("1+p+\cdots+p^a=\frac{p^{a+1} - 1}{p-1}");

を適用すれば、次が成り立つ。

&mimetex("\sigma(n)=\frac{p^{a+1} - 1}{p-1} \cdot \frac{q^{b+1} - 1}{q-1} \cdot\frac{r^{c+1} - 1}{r-1} \cdots"); □

例:n=496が完全数かどうかを調べる。

 nが完全数であれば「σ(n)=2n」が成り立つため、まずσ(n)を計算する。

496=2SUP{4};・31と素因数分解できるので、σ(496)は次のようにして計算できる。

σ(496)~
=&mimetex("\frac{2^{4+1}-1}{2-1} \cdot \frac{31^{1+1}-1}{31-1}");~
=(32-1)(31+1)
=31・2SUP{5};
=2×496

 したがって、496は完全数である。 □


*参考文献 [#j10d45e6]

-『工科系のための初等整数論入門 公開鍵暗号をめざして』