# 最大公约数与最小公倍数

在整数论中，最大公约数与最小公倍数是两个重要的概念
取整数 $a,b$，若整数 $d$ 满足

• $d \mid a$
• $d \mid b$
  则称 $d$ 为 $a,b$ 的一个 公约数

在所有公约数中，最大的那个称为 $a,b$ 的 最大公约数，记作 $\gcd(a,b)$

同样地，取整数 $m,n$，若整数 $l$ 满足

• $m \mid l$
• $n \mid l$
  则称 $l$ 为 $m,n$ 的一个 公倍数

在所有公倍数中，最小的那个称为 $m,n$ 的 最小公倍数，记作 $\mathrm{lcm}(m,n)$

# Euclidean 算法

Euclidean 算法是一种用于计算两个整数的最大公约数的有效算法
其原理基于以下性质

Euclidean 算法的步骤如下

1. 给定两个非负整数 $a$ 和 $b$，其中 $a \geq b$
2. 计算 $a$ 除以 $b$ 的余数 $r$
3. 如果 $r = 0$，则 $\gcd(a,b) = b$，算法结束
4. 否则，令 $a = b$，$b = r$，重复步骤 2 和 3

通过不断地用较小的数去除较大的数，并取余数，最终会得到最大公约数

# 扩张 Euclidean 算法

扩张 Euclidean 算法不仅可以计算最大公约数，还可以找到整数 $x,y$ 使得

$$ax + by = \gcd(a,b)$$

此算法尤其在求解线性同余方程时非常有用，特别是对于互质问题 $\gcd(a,b) = 1 \iff ax + by = 1$

通常利用矩阵代为计算，步骤如下

1. 给定两个非负整数 $a$ 和 $b$，其中 $a \geq b$
2. 设定矩阵

$$\begin{pmatrix} 1 & 0 & a \\ 0 & 1 & b \\ \end{pmatrix}$$

3. 通过反复行基本变换，每次用第一行减去第二行乘以某个整数，但是保证第三个数一直非负
4. 交换两行，重复步骤 3，直到第一行的第三个数为 $\gcd(a,b)$，第二行的第三个数为 $0$
5. 最终矩阵的第一行前两个数即为所求的 $x$ 和 $y$，即

$$\begin{pmatrix} x & y & \gcd(a,b) \\ m & n & 0 \\ \end{pmatrix}$$

其中 $x,y$ 满足 $ax + by = \gcd(a,b)$，$m,n$ 满足 $am + bn = 0$