- 追加された行はこの色です。
- 削除された行はこの色です。
*目次 [#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]
-『工科系のための初等整数論入門 公開鍵暗号をめざして』
