数论入门之路，从初学者到精通，有何捷径？

本文共计5157个文字，预计阅读时间需要21分钟。

数论概念基础+注：文本默认+（n/d）+为取整的除法方法。整除+定义：对于两个数+（a,b），我们称+（a/b）+，当且仅当存在一个+（k）+使得+（b=ak）。这个运算具有一些微妙的性质被称为性质。

数论 概念基础

注:本文默认 \(n/d\) 为下取整的除法。

整除

定义：对于两个数 \(a,b\) ，我们称 \(a|b\) ，当且仅当存在一个 \(k\) 使得 \(b=ak\) 。

这个运算有一些稍微值得被称为性质的性质，如下：

性质1

该运算具有传递性，即 \(a|b \and b|c\) 时，\(a|c\) 成立。

好像也没什么好说的性质了。

然后对于 \(a|b\) 的情况下，\(a\) 称为 \(b\) 的约数， \(b\) 称为 \(a\) 的倍数。

实际上所有数之间的关系可以用 \(b=ak+c~(0\le c< a)\) 表示，当 \(c=0\) 时，\(a|b\) 成立。 其中 \(c\) 称为余数。

最大公约数和最小公倍数

最大公约数（gcd）和 最小公倍数（lcm） ：字面意思，不多说了。

当 \(\gcd(a,b)=1\) ，那么我们称 \(a,b\) 互素。（多于两个数的情况也有这样类似的定义）

需要注意，多个数互素不一定他们两两互素。

求解gcd

如果求解 \(a,b\) 的 \(\gcd(a,b)\) ?

不妨钦定 \(a>b\) 。\(a|b\) 的情况答案直接是 \(a\) ，不考虑了，我们只考虑 \(a\not\mid b\) 的情况。