鉴于笨人没怎么学过数论，第一次学有些模糊，记个笔记加深一下印象，没有太多理解，更多是整理。主要内容来自于的离散数学以及助教，因而也许也可作为学习用。

裴蜀定理(Bézout’s Identity)

一个加仑的桶和一个加仑的桶能否精准称出加仑的水？假设你能精准地填满桶。可以这样，装满3加仑的，往5加仑的加，两次，最后倒满5加仑的，3加仑的就还剩1加仑。这实际上可以看做一个线性组合：

如果抽象一点呢，一个加仑的桶和一个加仑的桶，他们能否得到加仑的水？考虑一个特殊情况，6,9，那么直觉告诉我们，应该只会弄出来3的倍数。实际上，这也就是

是否有整数解。裴蜀定理即：其充要条件是是的倍数，表示最大公约数，通常省略直接用括号表示。

[!证明 ] 不妨设，若在两边同时取负号即可，若情形是的。

满足条件的是正整数的子集必有下确界，记符合条件的组成集合，考虑，我们可以写成带余除法的形式

其中是余数。移项就得到：

从而也可以被表出，从而或，前者与和是的最小值矛盾，从而只能有，也就是：

， 有

从而所有符合条件的数都是的倍数。下面证明：

令，则有符合条件，故，同理。从而是他们的公约数，下面证明是最大公约数。考虑任意公约数，有（表示x整除y），从而，从而。得证。

综上所述，命题成立。

我们也可以逆向进行一些数学的思考，利用上述，可以反过来给出的性质：

即其可被通过整数系数线性表出。意外的和线代有一点关联（

辗转相除法（欧几里得算法）

知道了能整出的水是最大公约数，如何计算呢？利用事实：允许我们辗转相除快速求出最大公约数。

[!证明] 不妨设。设，其中。我们要证明。我们考虑证明他们分别整除彼此来说明二者相等。先证明左边整除右边。不妨记左边是右边是，则从有，也就是说，那么就有或者，若实际上也有，又有从而。接下来证明右边整除左边。如法炮制即可，，从而如上可知成立。结合两方面得到原命题成立。

推论

1

若，且，则。

[!证明] 利用裴蜀定理，,同乘得到，由于左侧可被整除，故右侧也可以。

2

若，，且，则。

[!证明] 由，可设，从而，由推论得，故可设，则，故命题成立。

3

若 , 。

[!证明] 只需证明二者互相整除。设。一方面，，从而且，从而。另一方面，，由是约数以及推论，，，于是也有。综合两方面得到命题成立。

一些定义

互素(relatively prime)

如果和最大公约数为，即。

同余(congruent)

如果。写作。

逆元(inverse)

如果且，那么二者互为模意义的逆元。

裴蜀定理与逆元

裴蜀定理给出，，如果互素，那么有，从而我们有或者，也就是说，我们可以得到的逆元。

余数(remainder)

，则即为余数，即为。不难发现，。

密码学与数论

尽管计算机计算速度很快，但仍然有限。要计算一个大整数的质因数分解仍然很难，从而可以利用这一点对信息加密。

下面我们看两个简单的加密方法。

加密方法1

首先，把信息变成一个整数，例如，把字母从到编号，然后通过计算，适当地加上几个数字让其变为质数。接下来，选择一个很大的质数，加密方式就是。就是加密后的信息，只要质数足够大，就几乎无法破解。要解密只需要除以即可。

但设若一个人截获了两条信息，就有，那么只要计算就得到了密钥，这显然很不安全。

加密方法2

这一次，让。是质数。如果我们希望解密，利用余数与同余，我们有，如果存在，那么两边同乘即可得到，通过适当的选取，令则可确定。利用同余和余数的关系也可以写作。

设若一个人同时截获了，那么他此时也可以破解。

[!破解方法 ] 由于是质数，互素，从而我们可以得到，这里的便是模意义下的逆元。由两边同乘的逆元，得到。

更安全的加密

直觉上，也就需要更复杂的数学。

欧拉函数(Euler’s Totient Function)

通常记作，表示中与互素的数字个数。例如。

欧拉定理

尽管不知道有多少个欧拉定理这个欧拉定理是：

如 果 ， 那 么

证明：

[!Lemma1] 如果，那么证明：由于互素，利用裴蜀定理，可知存在，两侧同乘即得证结果。

[!Lemma2] 如果，那么记，设与互素，则有。证明： ①证明第一个集合也有个元素。设有重复，不妨设，则，由，则有，矛盾，故假设不成立，即第一个集合有个元素（互异）。 ②证明第一个集合的每个元素都与互素。考虑任意的，有，由于都与互素且非零，可知命题成立。综合①②，可知命题成立。

[!Proof] 现在，利用我们有;

利用，约去两边的，并回想起，就得到

这就完成了证明

第二个看似羚羊挂角无迹可寻，实际上可以视作把与互素的们乘上仍然互素，但为了限制在里取了个模，形式上就可以写成余数。这样实际上证明的核心在于取模后的数并不重复。然后我们运用“算两次”就得到了神奇的欧拉定理。尽管也很神奇，但这样看上去就至少不那么莫名其妙。据，这实际上是定理（群论）在模这个群里的特例，但我并不很清楚，也暂时不考虑直奔群论。简记于此。

费马小定理

令为质数，则，那么就有

这就是费马小定理。利用费马小定理我们可以直接得到的逆元，注意到，从而。

RSA加密

1. RSA 的数学地基

RSA 的安全性建立在一个简单的数论难题上：大整数分解。

把两个大质数和相乘得到非常快。
但只给你，想把它拆回却极其困难（当足够大时）。

2. 算法流程：如何利用欧拉定理？

第一步：准备“锁”和“钥匙”

选两个大质数，计算。
计算的欧拉函数值：。
选一个公钥指数（通常选 65537），要求。
关键点： 找到关于的模反元素。

也就是说，要满足：。

公钥（公开的锁）： - 私钥（藏好的钥匙）：

第二步：加密过程

假设你要发送消息：

这里就是密文。

第三步：解密过程（欧拉定理登场！）

接收方收到后，用私钥进行计算：

3. 为什么这个解密能成功？

这就是数学的神奇之处。我们将解密公式展开：

因为我们之前构造了，所以可以写成。

那么：

根据欧拉定理，，所以：

消息被完美还原了！

4. 为什么它是安全的？

攻击者知道： 和（公钥）。
攻击者想要： （私钥）。
阻碍： 要算出，攻击者必须先知道。
死胡同： 要知道，就必须知道和。也就是说，攻击者必须分解。

目前，分解一个 2048 位的 RSA 密钥在现实时间内是不可能的。