数论学习笔记

写在前面：

笔者一向认为，证明是学习数学的重中之重。证明不仅是一个逆向的过程，它可以成为一种正向的灵感， 或者方法， 或者技能， 可以推导出新的结论。数学不是一门面向结论的学科， 恰恰相反他是面向对象过程的。

然而， 笔者能力有限，不一定有精力给出所有证明， 所以：在一开始，我可能会仅限于结论， 或者只是感性的，不完全严谨的证明。因为这是一篇学习笔记， 证明会随着读者能力的提升不断完善，对算法的理解也会不断加深，而不急于一时。

毕竟， 暂时跳过是个不错的方法

但是， 在学习过程还是不能面向结论， 思想一定是学习的重点。

笔者过菜，本文仅写给自己复习用

gcd / lcm

\(gcd\): 两个整数的最大公因子是能整除它们的最大整数

首先我们有：

\(\gcd(0, n) = n\)

\(\gcd(a, b) = \gcd(b, a \ mod \ b)\)

    	对a, b的每个因子d, d|a且d|b, 所以d|(a mod b) (这等价于a - floor(a/b))
    	所以， 对于a，b的每个公因子，其必然也是b与a mod b 的公因子。故等式成立