約数の個数と約数の総和

方針：約数 $e$ と、$n=ec$ となる $c$ の素因数分解を並べると $n$ の素因数分解になる。素因数分解がただ 1 通りであること（素因数分解の一意性）から、$e$ の指数が $n$ の指数を超えないことを読み取る。
段 1（約数はこの形）。$e$ を $n$ の約数とし、$n=ec$ とする。$e$ と $c$ をそれぞれ素因数分解して並べると、$n$ の素因数分解が 1 つ得られる。一意性により、それは $p_1^{e_1}\cdots p_k^{e_k}$ と同じなので、$e$ に現れる素数は $p_1,\dots,p_k$ のどれかであり、$e$ の中の $p_i$ の指数 $f_i$ は、$n$ の中の指数 $e_i$ 以下である（$c$ の中の $p_i$ の指数との和が $e_i$ になるから）。よって $e=p_1^{f_1}\cdots p_k^{f_k}$、$0\le f_i\le e_i$ である。
段 2（この形なら約数）。$0\le f_i\le e_i$ なら、$c:=p_1^{e_1-f_1}\cdots p_k^{e_k-f_k}$ は整数で、$p_1^{f_1}\cdots p_k^{f_k}\cdot c=n$ なので、$p_1^{f_1}\cdots p_k^{f_k}$ は $n$ の約数である。
段 3（組が違えば数が違う）。$p_1^{f_1}\cdots p_k^{f_k}=p_1^{g_1}\cdots p_k^{g_k}$ なら、両辺は同じ数の素因数分解なので、一意性により各 $i$ で $f_i=g_i$ である。$\square$

方針：個数は lem-nsd-divisors の指数の組を数える。総和は、右辺の積を分配法則で展開した項が指数の組と 1 対 1 に対応することを使う。
段 1（個数）。lem-nsd-divisors により、約数の個数は組 $(f_1,\dots,f_k)$ の個数に等しい。$f_i$ は $0,1,\dots,e_i$ の $e_i+1$ 通りから独立に選べるので、積の法則により組は $(e_1+1)\cdots(e_k+1)$ 個ある。
段 2（展開）。積 $\prod_{i=1}^k(1+p_i+\cdots+p_i^{e_i})$ を分配法則で展開すると、各因子から 1 項 $p_i^{f_i}$（$0\le f_i\le e_i$）を選んで掛けた $p_1^{f_1}\cdots p_k^{f_k}$ を、すべての組 $(f_1,\dots,f_k)$ について 1 回ずつ足したものになる。
段 3（総和）。lem-nsd-divisors により、段 2 の項は $n$ の約数をちょうど 1 回ずつ尽くしている。よって展開の結果は $\sigma(n)$ である。
段 4（等比数列の和）。$(p-1)(1+p+\cdots+p^e)=(p+p^2+\cdots+p^{e+1})-(1+p+\cdots+p^e)=p^{e+1}-1$ なので、$1+p+\cdots+p^e=\dfrac{p^{e+1}-1}{p-1}$ である（等差数列と等比数列）。$\square$

方針：$m$ と $n$ に共通の素因数がないので、$mn$ の約数 $e$ は「$m$ の素数の部分」と「$n$ の素数の部分」にただ 1 通りに分かれる。これで $mn$ の約数と、組（$m$ の約数, $n$ の約数）が 1 対 1 に対応することを示す。
段 1（素因数分解を並べる）。$m=1$ なら $mn=n$ で、$d(1)=\sigma(1)=1$ なので等式は成り立つ。$n=1$ でも同じである。以下 $m,n\ge2$ とし、$m=p_1^{r_1}\cdots p_s^{r_s}$、$n=q_1^{u_1}\cdots q_t^{u_t}$ と素因数分解する。$m,n$ は互いに素なので、$p_i$ と $q_j$ に同じ素数はない（同じ素数があれば、それが $m$ と $n$ の公約数になる）。よって $mn=p_1^{r_1}\cdots p_s^{r_s}q_1^{u_1}\cdots q_t^{u_t}$ は $mn$ の素因数分解である。
段 2（1 対 1 対応）。lem-nsd-divisors により、$mn$ の約数は指数の組 $(f_1,\dots,f_s,g_1,\dots,g_t)$（$0\le f_i\le r_i$、$0\le g_j\le u_j$）と 1 対 1 に対応する。この組は、前半 $(f_1,\dots,f_s)$ と後半 $(g_1,\dots,g_t)$ の組に分けられ、前半は $m$ の約数 $a=p_1^{f_1}\cdots p_s^{f_s}$ に、後半は $n$ の約数 $b=q_1^{g_1}\cdots q_t^{g_t}$ に 1 対 1 に対応する（lem-nsd-divisors を $m$ と $n$ に使う）。$mn$ の約数 $e$ は $e=ab$ である。したがって、$e=ab$ という対応で、$mn$ の約数と、$m$ の約数 $a$ と $n$ の約数 $b$ の組 $(a,b)$ は 1 対 1 に対応する。
段 3（個数）。組 $(a,b)$ は $d(m)\,d(n)$ 個あるので、$d(mn)=d(m)\,d(n)$ である。
段 4（総和）。段 2 により
$$ \sigma(mn)=\sum_{e\mid mn}e=\sum_{a\mid m}\ \sum_{b\mid n}ab=\Bigl(\sum_{a\mid m}a\Bigr)\Bigl(\sum_{b\mid n}b\Bigr)=\sigma(m)\,\sigma(n) $$
である。3 つめの等号は、分配法則で右辺を展開すると、すべての組 $(a,b)$ の積 $ab$ の和になることによる。$d(1)=\sigma(1)=1$ なので、$d$ と $\sigma$ は乗法的である。$\square$

方針：prf-nsd-multiplicative の段 2 の対応 $e=ab$ を使い、$f(ab)=f(a)f(b)$ で和を積に分ける。
段 1。$F(1)=f(1)=1$ である。
段 2。$m,n$ を互いに素とする。prf-nsd-multiplicative の段 2 により、$mn$ の約数 $e$ は $e=ab$（$a\mid m$、$b\mid n$）とただ 1 通りに書ける。$a\mid m$、$b\mid n$ で $m,n$ が互いに素なので、$a,b$ も互いに素である（$a$ と $b$ の公約数は $m$ と $n$ の公約数だから $1$）。$f$ は乗法的なので $f(ab)=f(a)f(b)$ である。
段 3。よって
$$ F(mn)=\sum_{a\mid m}\ \sum_{b\mid n}f(a)f(b)=\Bigl(\sum_{a\mid m}f(a)\Bigr)\Bigl(\sum_{b\mid n}f(b)\Bigr)=F(m)\,F(n) $$
である。$\square$

方針：thm-nsd-formula の積 $\prod(e_i+1)$ が奇数になる条件を、指数 $e_i$ の偶奇に言いかえる。
段 1。整数の積が奇数であるのは、どの因数も奇数のときに限る（偶数の因数が 1 つでもあれば積は偶数、すべて奇数なら積も奇数）。よって $d(n)=\prod(e_i+1)$ が奇数 $\iff$ すべての $e_i+1$ が奇数 $\iff$ すべての $e_i$ が偶数である。
段 2。すべての $e_i$ が偶数なら、$m:=p_1^{e_1/2}\cdots p_k^{e_k/2}$ とおくと $n=m^2$ で、$n$ は平方数である。逆に $n=m^2$ なら、$m$ の素因数分解を 2 乗したものが $n$ の素因数分解なので（素因数分解の一意性）、$n$ の指数はすべて偶数である。$n=1$ では $d(1)=1$ は奇数で、$1=1^2$ は平方数である。$\square$

方針：thm-nsd-multiplicative により $\sigma(n)$ は素数の累乗ごとの因子 $\sigma(p^e)=1+p+\cdots+p^e$ の積である。各因子の偶奇を $p=2$ と奇数の素数に分けて調べる。
段 1（$p=2$ の因子）。$\sigma(2^a)=1+2+\cdots+2^a=2^{a+1}-1$ は、$a$ によらず奇数である。
段 2（奇数の素数の因子）。$p$ が奇数の素数なら、$1,p,\dots,p^e$ はどれも奇数である。奇数を $e+1$ 個足した和は、$e+1$ が奇数のとき奇数、偶数のとき偶数である。よって $\sigma(p^e)$ が奇数 $\iff$ $e$ が偶数である。
段 3（積）。$n=2^a\,p_1^{e_1}\cdots p_k^{e_k}$（$p_i$ は奇数の素数、$a\ge0$）とすると $\sigma(n)=\sigma(2^a)\,\sigma(p_1^{e_1})\cdots\sigma(p_k^{e_k})$ である。prf-nsd-parity-d の段 1 と同じく、積が奇数 $\iff$ すべての因子が奇数である。段 1・2 により、これは「すべての $e_i$ が偶数」と同値である。
段 4（言いかえ）。すべての $e_i$ が偶数とし、$m:=p_1^{e_1/2}\cdots p_k^{e_k/2}$ とおくと $n=2^am^2$ である。$a$ が偶数なら $n=(2^{a/2}m)^2$ は平方数、$a$ が奇数なら $n=2\,(2^{(a-1)/2}m)^2$ は平方数の $2$ 倍である。逆に $n=c^2$ または $n=2c^2$ なら、$c^2$ の指数はすべて偶数で、$2$ を掛けても変わるのは素数 $2$ の指数だけなので、奇数の素数の指数はすべて偶数である。$\square$