欧几里得算法、惟一分解定理

欧几里得算法（辗转相除法）求最大公约数GCD

有两个整数 $a,b(a>b)$ ，记它们的最大公约数为 $gcd(a,b)$，对于任意的 $a,b\ne 0$ 满足等式 ：

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

• 充分性证明：

  设 $d$ 为 $a,b$ 的最大公约数，那么有 $d\mid a$ 和 $d\mid b$ 成立，组合出 $d\mid (a-kb),\ (k\in N)$ 也成立，其中 $a-kb=a\%b$

• 必要性证明：

  设 $d$ 为 $a,a\% b$ 的最大公约数，那么有 $d\mid a$ 和 $d\mid (a-kb),\ (k\in N)$ 成立，同样可以组合出 $d\mid b$ 成立

程序设计中可以递归求解，递归出口为 $a,b=0$ ，其中不为 $0$ 的项即为最大公约数（$a>b$）

int gcd(int a, int b){
    if (b == 0) return a;
    return gcd(b, a % b);
}

• 复杂度分析：

  对 $a$ 取 $b$ 的模时，至少可以将 $a$ 缩小到 $a/2$ ，即 $a\% b \le a/2$ ，证明如下

  • $b< a/2$ 时，$a\% b<b< a/2$
  • $b>a/2$ 时，$a\%b=a-b\le a/2$
  • $b=a/2$ 时，$a\% b=0<a/2$ （特殊状况，$b$ 为 $a$ 因子）

最小公倍数LCM

有两个整数 $a,b(a,b\ne 0)$ ，记它们的最小公倍数为 $lcm(a,b)$，对于任意的 $a,b\ne 0$ 满足等式 ：

$$ lcm(a,b)=\frac{a\times b}{gcd(a,b)} $$

计算LCM需要先计算出GCD，采用先除后乘防止溢出

int lcm(int a, int b){
        return a / gcd(a, b) * b;
}

算数基本定理（整数惟一分解定理）

对于任意的一个正整数 $n$ ，有且仅有一种由质数的乘积所表达的方式

$$ n=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot\cdot\cdot p_s^{\alpha_s} \quad \quad p_1<p_2<\cdot \cdot\cdot<p_s $$

• $n$ 至多含有一个大于 $\sqrt{n}$ 的质因子

  根据上述的表达方式可以反推，若有两个大于 $\sqrt{n}$ 的质因子，它们的乘积一定大于了 $n$

• 证明LCM表达式

  设 ：

  $$ a=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot\cdot\cdot p_s^{\alpha_s} \\ b=p_1^{\beta_1}\cdot p_2^{\beta_2}\cdot\cdot\cdot p_s^{\beta_s} $$

  那么 $gcd(a,b)$ 与 $lcm(a,b)$ 可表示为

  $$ gcd(a,b)=p_1^{min(\alpha_1,\beta_1)}\cdot p_2^{min(\alpha_2,\beta_2)}\cdot\cdot\cdot p_s^{\min(\alpha_s,\beta_s)} $$

  $$ lcm(a,b)=p_1^{max(\alpha_1,\beta_1)}\cdot p_2^{max(\alpha_2,\beta_2)}\cdot\cdot\cdot p_s^{\max(\alpha_s,\beta_s)} $$

  因为满足以下的约束条件

  $$ min(\alpha_i,\beta_i)+max(\alpha_i,\beta_i)=\alpha_i+\beta_i $$

  所以有

  $$ gcd(a,b)\times lcm(a,b) =p_1^{\alpha_1+\beta_1}\cdot p_2^{\alpha_2+\beta_2}\cdot\cdot\cdot p_s^{\alpha_s+\beta_s} = a\times b $$