约数

Gorun · 2019-06-01 10:29:52 · 个人记录

约数

整除

设a，b是两个整数，且b≠0，如果存在整数c，是a=b*c，则称a被b整除，或b整除a，记作b|a。此时，又称a是b的倍数，b是a的因子。

这也就是说，a与b之间相差了c倍

设a,b是两个正整数，且b≠0，则存在唯一的整数q和r，使

a=qb+r(0\le r \lt |b|)

r=a\ mod\ b

再次发表一下个人见解，其实这一个式子就相当于我们小学的时候学过的

a \div b=q……r

性质：

若a|b且a|c，则对于所有x,y,有

a|xb+yc

b是a的倍数，c是a的倍数，任意倍b，c之和也是a的倍数

若a|b且a|c，则

a|c

这个性质可以概括为整除的传递性

设m≠0，则a|b，当且仅当

ma|mb

b是a的倍数，同时扩大/缩小m倍后，得到这个式子

若a|b且b|a，则

a =\pm b

约数

算数基本定理的推论

算数基本定理

任何一个大于1的正整数都能唯一分解为有限个质数的乘积：

N={p_1}^{c1}{p_2}^{c2}...{p_m}^{cm}

N的正约数个数为

(c_1+1)\times (c_2+1)\times ... \times (c_m+1)=\prod^{m}_{i=1}(c_i+1)

N的所有正约数和为

(1+p_1+p_1^2+...+p_1^{c_1})\times...(1+p_m+p_m^2+...+p_m^{c_m})
=\prod^m_{i=1}[\sum^{c_i}_{j=0}(p_i)^j]

根据乘法分配律，这样乘得意组合出所有的约数

求N的正约数集合——试除法