有理整数指的是整数环 $\mathbb Z$

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

在整数论中，最大公约数与最小公倍数是两个重要的概念
取整数 $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 算法的步骤如下

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 算法不仅可以计算最大公约数，还可以找到整数 $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$

# 同余方程

同余关系是一种在整数上的等价关系，为整数论的核心分析要素

取整数 $m$
若整数 $a,b$ 满足：$a-b$ 能被 $m$ 整除
则称 $a$ 与 $b$ 关于模 $m$ 同余 (Congruent modulo $m$)，记作

$$a \equiv b \pmod{m}$$

同余关系之间保有加法和乘法，即若 $a \equiv b \pmod{m},\ a' \equiv b' \pmod{m}$，则有

• $$a + a' \equiv b + b' \pmod{m}$$

• $$a a' \equiv b b' \pmod{m}$$

利用同余关系的性质，可以实现快速判断一个数字对 $9$ 或 $11$ 的同余关系
将整数 $a$ 写为十进制展开形式

$$a = a_n 10^n + a_{n-1} 10^{n-1} + \ldots + a_1 10 + a_0$$

由于 $10^k \equiv 1 \pmod{9}$，所以

$$a \equiv a_n + a_{n-1} + \ldots + a_1 + a_0 \pmod{9}$$

同理，由于 $10^k \equiv (-1)^k \pmod{11}$，所以

$$a \equiv \sum_{k=0}^{n} a_k (-1)^k \pmod{11}$$

---

同余方程指的是形如

$$f(x) \equiv 0 \pmod{m}$$

的方程，其中 $f(x)$ 为整数系数多项式

解同余方程的本质是解出符合同余关系的整数 $x$

若 $x$ 是同余方程 $f(x) \equiv 0 \pmod{m}$ 的解，那么关于模 $m$ 的等价类也是解

通常来说，同余方程最主要的是考察一次形式的多项式，即线性同余方程

$$ax \equiv b \pmod{m}$$

针对线性同余方程，其解的存在性由以下命题给出

解线性同余方程实际上是在利用 Euclidean 算法

# Euler 函数