数学：
证明方法：反证法，双向证明法
质因数
约数：
- 试除法
- 约数个数 (a1+1)(a2+1)...(an+1)=\(\prod_1^{约数个数} (a_i+1)\)
- 约数之和 (p1^0 +p1^1 +...+p1^a1)...=\(\prod_1^{约数个数} \sum_{i=0}^{每个约数重复次数a_i} (b^i)\)
gcd最大公约数——辗转相除法(欧几里得算法)
证明：gcd(a,b) = gcd(b,a%b)
4|2，竖杠代表能整除
设a%b = a - kb 其中k = a/b(向下取整)
若d是(a,b)的公约数 则知 d|a 且 d|b 则易知 d|a-kb 故d也是(b,a%b) 的公约数
若d是(b,a%b)的公约数 则知 d|b 且 d|a-kb 则 d|a-kb+k*b = d|a 故而d同时整除a和b 所以d也是(a,b)的公约数
(双向证明)
因此(a,b)的公约数集合和(b,a%b)的公约数集合相同 所以他们的最大公约数也相同 证毕
- 最小公倍数
快速幂
标签：约数,kb,p1,a%,gcd,算法,数学,公约数 From： https://www.cnblogs.com/nolca/p/17386933.html