数论再谈有哪些新进展？

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

计算最大公约数和最小公倍数。给定两个整数a和b，最大公约数为gcd(a, b)，最小公倍数为lcm(a, b)。设a+b。求最大公约数gcd(a, b)=gcd(b, a mod b)。证明如下：

最大公约数 和 最小公倍数

记 \(a\) 和 \(b\) 最大公约数为 \(\gcd(a, b)\), 记 \(a\) 和 \(b\) 最小公倍数数为 \(lcm(a, b)\)。
设 \(a > b\)。

求最大公约数

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

证明

如果 \(a\) 是 \(b\) 的倍数， 那么 \(\gcd(a,b) = b\)，如果 \(b = 0\)， 那么 \(\gcd(a, b) = a\)。

下面讨论 \(a\) 不是 \(b\) 的倍数的情况。

设 \(a = bk + r\)，那么 \(a \mod b = r\)，就是要证明 \(\gcd(a, b) = \gcd(b, r)\)。

记 \(\gcd(a, b) = x\)， 于是就有 \(a | x\)， \(b | x\)。

把上面的式子变一下，就是 \(r = a - bk\)，同时除以一个 \(x\)，于是 \(\frac{r}{x} = \frac{a}{x} - \frac{bk}{x}\)。