目录
约数
约数即是因数，我们定义对于正整数 (n,m) ，若 (exist kin Z_+) 使得 (n=m imes k)
则，我们称 (m) 为 (n) 的约数
对称的， (k) 也为 (n) 的因数
整除
若正整数 (m) 为正整数 (n) 的因数，则对于带余除法式子的形式： (ndiv m=kcdots r(0leq r<m) 且 (k,rin Z_+)) 一定有 (r=0)
因此，我们认为 (n) 除以 (m) 为不带余的整数，或者称 (m) 除 (n) 为不带余的整数
也就是 (m) 整除 (n) ，记作 (mmid n)
对于 (r eq 0) 的式子，我们称 (m) 不整除 (n) ，记作 (m mid n)
约数的判断
由算数基本定理，我们可以得知，对 (forall a>1,a,c_iin Z_+,a=p_1^{c_1}p_2^{c_2}p_3^{c_3}cdots p_m^{c_m}) 存在唯一表示方法
那么只有对于 (forall d_ileq c_i,d_iin N,(p_1^{d_1}p_2^{d_2}p_3^{d_3}cdots p_m^{d_m})mid a)
我们先证明存在性：
记 (displaystyle a=prod_{i=1}^mp_i^{c_i},b=prod_{i=1}^mp_i^{d_i},e_i=c_i-d_i)
由于 (d_ileq c_i)
故 (e_i=c_i-d_ileq 0)
因此 (p_i^{e_i}) 一定为整数
记 (displaystyle c=prod_{i=1}^mp_i^{e_i})
则 (a=b imes c) ，因此 (b) 为 (a) 的约数
由于证明对 (forall d_ileq c_i) 成立，故对所有符合上述条件的 (b) 均成立
再证明唯一性：
若 (b) 引入了新的质数，则对应的质数 (a) 不含有，故同上设置的 (c) 存在负数次方项，不为整数
因此若 (b) 需为 (a) 的因数，则不含有 (a) 的质因数以外的质因数
同样记 (displaystyle a=prod_{i=1}^mp_i^{c_i},b=prod_{i=1}^mp_i^{d_i},e_i=c_i-d_i)
若 (exist d_i>c_i) 则对应的 (e_i<0)
故 (p_i^{e_i}) 不为整数，因此 (displaystyle prod_{i=1}^mp_i^{e_i}) 不为整数
此时 (b) 同样不为 (a) 的因数
综上，上述定理成立
约数的个数
我们习惯用字母 (oldsymbol d(n)) 或 (oldsymbol sigma_0(n)) 表示
根据定义，我们可以列出表达式 (displaystyle oldsymbol sigma_0(n)=sum_{dmid n}1)
考虑若 (n=1) 时，显然有 (oldsymbol sigma_0(1)=1)
而对于 (n=p_1^{c_1}p_2^{c_2}p_3^{c_3}cdots p_m^{c_m},forall c_iin Z_+)
对于 (d_m) 的选择 (0,1,2cdots c_m) ，与其它 (d_i) 都是相互独立的
因此 (displaystyle oldsymbol sigma_0(n)=sum_{dmid n}1=(sum_{dmid{nover p_m^{c_m}}}1) imes (sum_{dmid p_m^{c_m}}1)=oldsymbol sigma_0({nover p_m^{c_m}})cdotoldsymbol sigma_0(p_m^{c_m}))
而对于 (displaystyle oldsymbol sigma_0(p_m^{c_m})=sum_{dmid p_m^{c_m}}1=sum_{k=0}^{c_m}1=(c_m+1))
因此 (displaystyle oldsymbol sigma_0(n)=oldsymbol sigma_0({nover p_m^{c_m}})cdotoldsymbol sigma_0(p_m^{c_m})=oldsymbol sigma_0({nover p_m^{c_m}})cdot(c_m+1)=cdots=prod_{i=1}^m(c_i+1)cdotoldsymbol sigma_0(1)=prod_{i=1}^m(c_i+1))
这是一个重要结论：(displaystyle oldsymbol sigma_0(prod_{i=1}^mp_i^{c_i})=prod_{i=1}^m(c_i+1))
约数的和
我们习惯用 (oldsymbol sigma_1(n)) 或 (oldsymbol sigma(n)) 来表示 (n) 的因数和
同样根据定义，我们得到 (displaystyle oldsymbol sigma(n)=sum_{dmid n}d)
显然 (oldsymbol sigma(1)=1)
同样是考虑到了质数间的独立性，我们可以得到 (oldsymbol sigma(n)=oldsymbol sigma({nover p_m^{c_m}})cdot oldsymbol sigma(p_m^{c_m}))
而单独考虑 (displaystyle oldsymbol sigma(p_m^{c_m})=sum_{dmid p_m^{c_m}}d=sum_{k=0}^{c_m}p_m^k)
因此，同上分析，我们得到了 (displaystyle oldsymbol sigma(prod_{i=1}^mp_i^{c_i})=prod_{i=1}^m(sum_{k=0}^{c_i}p_i^k))
或者可以用等比数列公式化简：
(displaystyle sum_{k=0}^{c_i}p_i^k={1-p_i^{c_i+1}over 1-p_i})
(displaystyle herefore sigma(prod_{i=1}^mp_i^{c_i})=prod_{i=1}^m{1-p_i^{c_i+1}over 1-p_i})
约数的次方和
我们习惯用 (oldsymbol sigma_k(n)) 表示 (n) 的约数的 (k) 次方和
即 (displaystyle oldsymbol sigma_k(n)=sum_{dmid n}d^k)
所以，同上分析，我们可以得到公式 (displaystyle oldsymbol sigma_k(prod_{i=1}^mp_i^{c_i})=prod_{i=1}^m(sum_{j=0}^{c_i}p_i^{kj}))
考虑 (k=0) 时：
(displaystyle sum_{j=0}^{c_i}p_i^{0 imes j}=sum_{j=0}^{c_i}1=c_i+1)
再考虑 (k eq 0) 时
(displaystyle sum_{j=0}^{c_i}p_i^{kj}={1-p_i^{k(c_i+1)}over 1-p_i^k})
因此得到公式：
(displaystyle oldsymbol sigma_k(prod_{i=1}^mp_i^{c_i})= egin{cases} displaystyle prod_{i=1}^m(c_i+1),k=0 \ \ displaystyle prod_{i=1}^m{1-p_i^{k(c_i+1)}over 1-p_i^k},k eq 0 end{cases})
代入后发现，实际上 (oldsymbol sigma(n)) 为 (k=1) 特例，(oldsymbol d(n)) 为 (k=0) 特例