鉴于笨人没怎么学过数论，第一次学有些模糊，记个笔记加深一下印象，没有太多理解，更多是整理。主要内容来自于 $mit$的离散数学以及$Gemini$ 助教，因而也许也作为学习用。
裴蜀定理(Bézout’s Identity)
一个 $3$加仑的桶和一个$5$加仑的桶能否精准称出$1$ 加仑的水？假设你能精准地填满桶。
可以这样，装满3加仑的，往5加仑的加，两次，最后倒满5加仑的，3加仑的就还剩1加仑。
这实际上可以看做一个线性组合：
$$ 1=2\cdot 3+(-1) \cdot 5 $$
如果抽象一点呢，一个 $a$加仑的桶和一个$b$加仑的桶，他们能否得到$c$ 加仑的水？
考虑一个特殊情况，6,9，那么直觉告诉我们，应该只会弄出来3的倍数。
实际上，这也就是
$$ ax+by=c $$
是否有整数解。
裴蜀定理即：其充要条件是 $c$是$gcd(a,b)$ 的倍数，$gcd$表示最大公约数，通常省略$gcd$直接用括号$(a,b)$ 表示。
[!证明 ]
不妨设 $c>0$，若 $c<0$在两边同时取负号即可，若$c=0$情形是$trivial$ 的。
满足条件的 $c$是正整数的子集必有下确界$d$，记符合条件的$c$组成集合$S$，考虑$m \neq d \in S$ ，我们可以写成带余除法的形式
$$ m=kd+r $$
其中 $r < d$ 是余数。移项就得到：
$$ r=m-kd $$
从而 $r$也可以被$a,b$表出，从而$r \in S$或$r=0$，前者与$r<d$和$d$是$S$的最小值矛盾，从而只能有$r=0$ ，也就是：
$$ \forall m \in S,m\neq d，有 m=kd $$
从而所有符合条件的数都是 $d$ 的倍数。
下面证明 $d=gcd(a,b)$：
令 $c=a$，则有$(x,y)=(1,0)$符合条件，故$a \in S$，同理$b \in S$。从而$d$是他们的公约数，下面证明是最大公约数。考虑任意公约数$g$，有$g|ax+by$（$x|y$表示x整除y），从而 $g|d$，从而$g \leq d$ 。得证。
综上所述，命题成立。
我们也可以逆向进行一些数学的思考，利用上述，可以反过来给出 $gcd$ 的性质：
$$ gcd(a,b)=ax+by $$
即其可被 $a,b$ 通过整数系数线性表出。意外的和线代有一点关联（
辗转相除法（欧几里得算法）
知道了能整出的水是最大公约数，如何计算呢？利用事实：
$\gcd(a, b) = \gcd(b, a \bmod b)$
允许我们辗转相除快速求出最大公约数。
[!证明]
不妨设 $a \leq b$ 。
设 $a = qb + r$，其中 $r = a \bmod b$。我们要证明 $\gcd(a, b) = \gcd(b, r)$。
我们考虑证明他们分别整除彼此来说明二者相等。
先证明左边整除右边。不妨记左边是 $x$右边是$y$， 则从 $a=qb+r$有$k_1x = k_2x + r$，也就是说$r=(k_1-k_2)x$，那么就有$r=0,a=qb$或者$x|r$，若$r=0$实际上也有$x|r$，又有$x|b$从而$x|gcd(b,r)=y$。
接下来证明右边整除左边。如法炮制即可，$a=(k_3+k_4)y$，从而如上可知成立。
结合两方面得到原命题成立。
推论
1
若 $a|bc$，且$(a,b)=1$，则$a|c$ 。
[!证明]
利用裴蜀定理，$au+bv=1$,同乘$c$得到$acu+bvc=c$，由于左侧可被$a$ 整除，故右侧也可以。
2
若 $a|c$ ，$b|c$，且$(a,b)=1$，则$ab|c$ 。
[!证明]
由 $a|c$，可设$c=qa$，从而$b|c=qa$，由推论$1$得$b|q$，故可设$q=mb$，则$c=mab$ ，故命题成立。
3
若 $(a,b)=1$,$(a,bc)=(a,c)$ 。
[!证明]
只需证明二者互相整除。
设 $d_1=(a,bc),d_2=(a,c)$ 。
一方面， $d_2|a,d_2|c$，从而$d_2|bc$且$d_2|a$，从而$d_2|d_1$ 。
另一方面，$d_1|bc$，由$d_1$是$a$约数以及推论$1$ ，$(d_1,b)=1$ ，$d_1|c$，于是也有$d_1|d_2$ 。
综合两方面得到命题成立。
一些定义
互素(relatively prime)
如果 $a$和$b$最大公约数为$1$，即$\exists x, y \in Z , st, ax+by=1$ 。
同余(congruent)
如果 $n|(a-b)$。写作$a \equiv b \pmod n$ 。
逆元(inverse)
如果 $xx^{-1} \equiv 1 \pmod{n}$且$x^{-1} \in {1,2,…,n-1}$ ，那么二者互为模意义的逆元。
裴蜀定理与逆元
裴蜀定理给出，$gcd(a,b)=ax+by$，如果$a,b$互素，那么有$ax+by=1$，从而我们有$ax\equiv 1 \pmod y$或者$by \equiv 1 \pmod x$，也就是说，我们可以得到$a,b$ 的逆元。
余数(remainder)
$m=kd+r$，则$r$即为余数，即为$rem(m,d)$。不难发现，$rem(m,d) \equiv m \pmod d$ 。
密码学与数论
尽管计算机计算速度很快，但仍然有限。要计算一个大整数的质因数分解仍然很难，从而可以利用这一点对信息加密。
下面我们看两个简单的加密方法。
加密方法1
首先，把信息变成一个整数 $m$，例如，把字母从$01$到$26$编号，然后通过计算，适当地加上几个数字让其变为质数。接下来，选择一个很大的质数$k$，加密方式就是$m’=mk$ 。$m’$就是加密后的信息，只要质数足够大，就几乎无法破解。要解密只需要除以$k$ 即可。
但设若一个人截获了两条信息，就有 $m_1’=m_1k, m_2’=m_2k$，那么只要计算$gcd(m,m’)$就得到了密钥 $k$ ，这显然很不安全。
加密方法2
这一次，让 $m’=rem(mk,p)$ 。$p$ 是质数。
如果我们希望解密，利用余数与 $m’$同余，我们有$m’ \equiv mk \pmod p$，如果$k^{-1}$存在，那么两边同乘即可得到$m \equiv m’ \cdot k^{-1} \pmod p$，通过适当的选取，令$m<p$则可确定$m$ 。
利用同余和余数的关系也可以写作 $m=rem(m’k^{-1},p)$ 。
设若一个人同时截获了 $m,m’$，那么他此时也可以破解$k$ 。
[!破解方法 ]
由于 $p$ 是质数，$m,p$互素，从而我们可以得到$\exists x,y \in Z ,mx+py=1$，这里的 $x$便是模$p$意义下$m$ 的逆元。
由 $m’ \equiv mk \pmod p$两边同乘$m$的逆元，得到$k\equiv m’m^{-1} \pmod p$ 。
更安全的加密
直觉上，也就需要更复杂的数学。
欧拉函数(Euler’s Totient Function)
通常记作 $\phi(n)$，表示${1,2,…,n-1}$中与$n$ 互素的数字个数。
例如 $\phi(12)=4,\phi(15)=8$。
欧拉定理
尽管不知道有多少个欧拉定理
这个欧拉定理是：
$$ 如果gcd(n,k)=1，那么k^{\phi(n)}\equiv 1 \pmod n $$
证明：
[!Lemma1]
如果 $gcd(n,k)=1$，那么$ak \equiv bk \pmod n$ $\implies$ $a\equiv b \pmod n$
证明：
由于 $n,k$互素，利用裴蜀定理，可知$k^{-1}$ 存在，两侧同乘即得证结果。
[!Lemma2]
如果 $gcd(n,k)=1$，那么记$r=\phi(n)$，设$k_1,…,k_r$与$n$互素，则有${rem(k_1k,n),…rem(k_rk,n)}={k_1,…,k_r}$。
证明：
①证明第一个集合也有 $r$ 个元素。
设有重复，不妨设 $k_i\neq k_j , rem(k_ik,n)=rem(k_jk,n)$，则$k_ik\equiv k_jk \pmod n$，由$Lemma1$，则有$k_i=k_j$，矛盾，故假设不成立，即第一个集合有$r$ 个元素（互异）。
②证明第一个集合的每个元素都与 $n$ 互素。
考虑任意的 $k_i$，有$rem(k_ik, n)\equiv k_ik \pmod n$，由于$k_i,k$都与$n$ 互素且非零，可知命题成立。
综合①②，可知命题成立。
[!Proof]
现在，利用 $Lemma2$ 我们有;
$$ \begin{aligned} k_1 \cdot k_2 \cdot \cdot \cdot k_r&=rem(k_1k,n) \cdot rem(k_2k,n) \cdot \cdot \cdot rem(k_3k,n) \\ &\equiv k_1k \cdot k_2k \cdot \cdot \cdot k_rk \pmod n \\ &\equiv k_1 \cdot k_2 \cdot \cdot \cdot k_r \cdot k^r \pmod n\end{aligned} $$
利用 $Lemma1$，约去两边的$k_1 \cdot k_2 \cdot \cdot \cdot k_r$，并回想起$r=\phi(n)$ ，就得到
$$ k^{\phi(n)}\equiv 1 \pmod n $$
这就完成了证明
第二个 $Lemma$看似羚羊挂角无迹可寻，实际上可以视作把与$n$互素的$k_i$们乘上$k$仍然互素，但为了限制在$n$ 里取了个模，形式上就可以写成余数。这样实际上证明的核心在于取模后的数并不重复。然后我们运用“算两次”就得到了神奇的欧拉定理。尽管也很神奇，但这样看上去就至少不那么莫名其妙。
据 $Gemini$，这实际上是$Lagrange$ 定理（群论）在模这个群里的特例，但我并不很清楚，也暂时不考虑直奔群论。简记于此。
费马小定理
令 $p$为质数，则$\phi(p)=p-1$ ，那么就有
$$ k^{p-1}\equiv1 \pmod p $$
这就是费马小定理。
利用费马小定理我们可以直接得到 $k$的逆元，注意到$k^{p-1}=kk^{p-2}$，从而$k^{-1}=k^{p-2}$ 。
RSA加密
1. RSA 的数学地基
RSA 的安全性建立在一个简单的数论难题上：大整数分解。
把两个大质数 $p$和$q$相乘得到$n$ 非常快。
但只给你 $n$，想把它拆回 $p \times q$却极其困难（当$n$ 足够大时）。
2. 算法流程：如何利用欧拉定理？
第一步：准备“锁”和“钥匙”
选两个大质数 $p, q$，计算 $n = p \times q$。
计算 $n$ 的欧拉函数值：$\phi(n) = (p-1)(q-1)$。
选一个公钥指数 $e$（通常选 65537），要求 $gcd(e, \phi(n)) = 1$。
关键点： 找到 $e$关于$\phi(n)$的模反元素$d$。
也就是说，要满足：$e \cdot d \equiv 1 \pmod{\phi(n)}$。
- 公钥（公开的锁）： $(n, e)$- 私钥（藏好的钥匙）：$(n, d)$
第二步：加密过程
假设你要发送消息 $M$：
$$ C = M^e \pmod n $$
这里 $C$ 就是密文。
第三步：解密过程（欧拉定理登场！）
接收方收到 $C$后，用私钥$d$ 进行计算：
$$ M = C^d \pmod n $$
3. 为什么这个解密能成功？
这就是数学的神奇之处。我们将解密公式展开：
$$ C^d = (M^e)^d = M^{ed} \pmod n $$
因为我们之前构造了 $ed \equiv 1 \pmod{\phi(n)}$，所以可以写成 $ed = k \cdot \phi(n) + 1$。
那么：
$$ M^{ed} = M^{k\phi(n) + 1} = (M^{\phi(n)})^k \cdot M^1 \pmod n $$
根据欧拉定理，$M^{\phi(n)} \equiv 1 \pmod n$，所以：
$$ (1)^k \cdot M \equiv M \pmod n $$
消息被完美还原了！
4. 为什么它是安全的？
攻击者知道： $n$和$e$（公钥）。
攻击者想要： $d$（私钥）。
阻碍： 要算出 $d$，攻击者必须先知道 $\phi(n)$。
死胡同： 要知道 $\phi(n)$，就必须知道 $p$和$q$。也就是说，攻击者必须分解 $n$。
目前，分解一个 2048 位的 RSA 密钥在现实时间内是不可能的。