Open ganmouren opened 5 years ago
https://ganmouren.github.io/Number_theory/#more
这里会简单记录我学习的基础数论。这里的证明可能都不大严谨，仅供参考。 欧几里得算法如果我们想要求 $gcd(a,b)(a\text{与}b$的最大公因数$)$ ，最简单的方式便是枚举，但这太慢了。于是我们有了我们的辗转相除法，也就是欧几里得算法，它可以在 $O(log_2b)$ 的复杂度内求出 $gcd(a,b)$ 。$$gcd(a,b) = gcd(b,a\bmod b)$$ 证明设 $r=a\
https://ganmouren.github.io/Number_theory/#more
这里会简单记录我学习的基础数论。这里的证明可能都不大严谨，仅供参考。 欧几里得算法如果我们想要求 $gcd(a,b)(a\text{与}b$的最大公因数$)$ ，最简单的方式便是枚举，但这太慢了。于是我们有了我们的辗转相除法，也就是欧几里得算法，它可以在 $O(log_2b)$ 的复杂度内求出 $gcd(a,b)$ 。$$gcd(a,b) = gcd(b,a\bmod b)$$ 证明设 $r=a\