引言

gcd 有目前几条性质：

性质1

\(a \cdot b = lcm(a,b) \cdot gcd(a,b)\)

证明：

设 \(d = gcd(a,b)\)，则有 \(a= a_0 \cdot d\)，\(b = b_0 \cdot d\)

由于 \(gcd(a_0,b_0) = 1\)

并且 \(lcm(a_0,b_0) = a_0 \cdot b_0\)

则有 \(a \cdot b = a_0 \cdot b_0 \cdot d = lcm(a,b) \cdot gcd(a,b)\)

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

设 \(d = gcd(a,b)\)，则有 \(a = md\)，\(b = nd\)，且 \(gcd(m,n)= 1\)

则有 \(gcd(a,a-b) = gcd(md,md-nd) = d * gcd(m,m-n) = d\)

所以 \(gcd(a,b) = gcd(a,a-b)\)

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

设 \(d = gcd(a,b)\)，则有 \(a = md\)，\(b = nd\)，且 \(gcd(m,n)= 1\)

则有 \(gcd(a,a+b) = gcd(md,md+nd) = d * (m,m+n) = d\)

所以 \(gcd(a,b) = gcd(a,a+b)\)

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

设 \(a = k \cdot b + r\)，则有 \(r = a - k \cdot b\)

设 \(gcd(a,b) = d\)

则由 \(r = a - k \cdot b = n \cdot d - k \cdot m \cdot d = (n - k \cdot m) \cdot d\)

所以 d 是 r 的因数，因此 d 是 b 和 r 的公因数

由于 \(r = a \% b\)，则可证 \(gcd(a,b) = gcd(b,a%b)\)