裴蜀定理,一次不定方程,费马小定理,欧拉定理の总结

· · 算法·理论

裴蜀定理

定义

裴蜀定理是数论中的一个基本定理。它表明，对于任意两个整数 a 和 b，以及它们的最大公约数 d，存在整数 x 和 y 使得：

a\times x+b\times y=d

性质

  3. 如果 a 和 b 互质，则 d=1，此时存在整数 x,y 使得 a\times x+b\times y=1。

    证明

设 S 是所有形如 a \times x+b\times y 的整数的集合，其中 x,y\in\mathbb{Z}。

$S$ 中的正整数有下界，因此 $S$ 中的正整数的最小值记为 $d$。 由 $d\in S$，存在整数 $x_{0}, y_{0}$ 使得 $a\times x_{0}+b\times y_{0}=d$。 $d$ 是 $a$ 和 $b$ 的**公约数**，因为 $d\mid a$ 且 $d\mid b$。 由于 $d$ 是 $a$ 和 $b$ 的线性组合，$d$ 是它们的**最大公约数**。 因此，**裴蜀定理得证**。 ---- ## 一次不定方程 ### 定义 一次不定方程是指形如 $a\times x+b\times y=c$ 的方程，其中 $a,b,c\in\mathbb{Z}$。 ### 性质 1. 方程有整数解的充要条件是 $\gcd(a,b)\mid c$。 2. 解的形式是**无穷多个**，且可以表示为一般解： $$x=x_{0}+k\times\frac{b}{d},y=y_{0}-k\times\frac{a}{d},k\in\mathbb{Z}$$ 其中，$d=\gcd(a,b)$，$(x_{0},y_{0})$ 是**特解**。 ### 计算公式 1. 使用**扩展欧几里得算法**求解 $a\times x_{0}+b\times y_{0}=\gcd(a,b)$。 2. 如果 $\gcd(a,b)\mid c$，则将特解扩展为 $a\times x+b\times y=c$。 ---- ## 费马小定理 ### 定义 **费马小定理**是数论中的一个重要定理。它表明，如果 $p$ 是一个质数，且 $a$ 是一个整数，满足 $p\nmid a$，则： $$a^{p-1}\equiv 1\pmod{p}$$ ### 性质 1. 费马小定理是模运算中的一个**基本性质**。 2. 如果 $a$ 是 $p$ 的倍数，则 $a^{p-1}\equiv 0\pmod{p}$。 3. 费马小定理是欧拉定理的特例。 ### 计算公式 1. $a^{p-1}\bmod p=1$（当 $p\nmid a$ 时）。 2. 可以用于**快速求解模幂**。 ### 证明 考虑模 $p$ 的剩余类 $\{1,2,\dots,p-1\}$。 设 $S=\{a,2a,\dots,(p-1)a\}$，其中每个元素对 $p$ 取模。 由于 $p$ 是素数，且 $p\nmid a$，$S$ 中的元素模 $p$ 后是 $\{1,2,\dots,p-1\}$ 的一个排列。 因此： $$(1\times 2\times\dots\times(p-1))\times a^{p-1}\equiv 1\times 2\times\dots\times(p-1)\pmod{p}$$ 消去公共因子 $1\times 2\times\dots\times(p-1)$，得到： $$a^{p-1}\equiv 1\pmod{p}$$ **费马小定理得证**。 ---- ## 欧拉定理 ### 定义 欧拉定理是费马小定理的推广。它表明，如果 $a$ 和 $n$ 互质，则： $$ a^{\phi(n)}\equiv 1\pmod{n} $$ 其中，$\phi(n)$ 是欧拉函数，表示小于 $n$ 且与 $n$ 互质的正整数个数。 ### 性质 1. 如果 $n$ 是素数，则 $\phi(n)=n-1$，欧拉定理退化为费马小定理。 2. 欧拉定理可以用于计算大整数的模幂。 3. 如果 $a$ 和 $n$ 不互素，则 $a^{\phi(n)}\not\equiv 1\pmod{n}$。 ### 计算公式 1. $\phi(n)$ 的计算： $$\phi(n)=n\times\prod_{p\mid n}\left(1-\frac{1}{p}\right)$$ 其中，$p$ 是 $n$ 的所有质因子。 2. $a^{\phi(n)}\bmod n=1$（当 $a$ 和 $n$ 互质时）。 ### 证明 设 $\{x_{1}, x_{2},\dots,x_{\phi(n)}\}$ 是小于 $n$ 且与 $n$ 互质的整数。 考虑集合 $S=\{a\times x_1,a\times x_2,\dots,a\times x_{\phi(n)}\}$，其中每个元素对 $n$ 取模。 由于 $a$ 和 $n$ 互质，$S$ 中的元素模 $n$ 后是 $\{x_{1},x_{2},\dots,x_{\phi(n)}\}$ 的一个排列。 因此： $$ x_{1}\times x_2\times\dots\times x_{\phi(n)}\times a^{\phi(n)}\equiv x_1\times x_2\times\dots\times x_{\phi(n)}\pmod{n} $$ 消去公共因子 $x_1\times x_2\times\dots\times x_{\phi(n)}$，得到： $$a^{\phi(n)}\equiv 1\pmod{n}$$ **欧拉定理得证**。 ::::info[AI 使用说明]{open} 本文章在写作完成后使用 ChatGPT 进行了润色。 :::: ## Update - 更改了数学公式的问题。 - 更改了取模运算上的问题。 - 更改了有序列表和无序列表的问题的问题