写给自己看，大佬们请移步，谢谢~

没有人可以请教真的是太痛苦了，大哭。

参考书：Kenneth H. Rosen《初等数论及其应用第六版》

学了一天回到宿舍后，看了看刚发下来的课本，原来《信息安全数学基础》这门课学的就是初等数论，那我还自学干嘛。。。直接听老师讲吧。

本文基本不再更新，除非有些知识是课堂上不涉及的。

如有课堂笔记我会另开一贴。（flag已立）。说实话，除了韩老师的课之外，我很多专业课也大都是水下来的。忏悔一秒种。

符号表

第二章

乘法

明天写

除法

明天写

第三章

3.3 最大公因子及其性质

P69 定理3.7

推导中使用的是公因子，而不是最大公因子。

所以我的理解是，(a, b)和(a + cb, b)的所有公因子均相同。

因而自然会有最大公因子gcd(a, b) = gcd(a + cb, b)

P69 定理3.8

证明出整数r是a, b的线性组合之后的一步，我的理解是这样的：

整理出r = a - dq = a - q(ma + nb) = (1 - qm)a - qmb

由带余除法的定义式可知，余数r必然满足0 <= r < d

注意，r是a, b的线性组合，因为1 - qm和 -qm都是整数。既然是a, b的线性组合，那自然也满足我们前面假设的d是a,b的线性组合的最小的正整数这一条件。

所以r的最小正整数取值为d，但是不等式的右边又取不到等号，那就只能取0了。

一但r取0，就意味着前面的带余除法的等式中的余数为0，即d整除a.

P71 定理3.9

有R = {ma+nb | m,n属于Z} ,S = {gcd(a, b) * k | k属于Z}，证R = S

即证R包含于S，且S包含于R.

前者：

记d是a,b的最大公因子，所以d|a且d|b，所以d|(ma+nb)，即有ma+nb = kd，注意，这里并不能直接推出R = S，因为此处的k并不一定会包含整数集内的所有整数，所以等式右边只是S中的一部分元素，因此只能推出R包含于S.

后者：

由定理3.8，一定存在r,s使得d = ra+sb（a,b的最大公因子是a,b的线性组合的最小正整数），所以有jd = jra + jsb。j是整数集内所有元素，但是jr和js未必能够遍历整数集，所以这里推出S是R的一部分，即S包含于R.

二者结合，证毕。

P71 定理3.10

本定理较易理解，可概括为：两个不全为零的整数a,b的最大公因子是能被其他所有的公因子整除的正公因子。

有几个点需要注意：

• 是正公因子。比如15和25的最大公因子是5，但是-5也是他俩的公因子，只不过是最小的。
• 如果某个公因子不能被另一个公因子整除，那么一定会有一个更大的公因子，即这二者的最小公倍数（我觉得哈。

P72

两两互素的条件比互素的条件强。

前者可推后者，反之不可

3.4 欧几里得算法

P75 欧几里得算法

原理是定理3.7：gcd(a+bc, b) = gcd(a, b)

按照这个原理，每次运算时，将较大的那个参数表示成带余除法的形式（a+bc），注意该形式中两个相乘的数，有一个必须是较小的那个参数b（这样才能满足定理3.7的形式啊），即带余除法的除数。然后用余数a代替原来的较大的那个参数，求余数a与除数b的最大公因子。

提问，为啥要将较大的那个参数表示成带余除法的形式呢？表示较小的那个数不行吗？

当然不行，但是你这样做就不是优化运算了，反倒是复杂化运算了。

比如gcd(x=ky+r, y), x<y,可以等效成gcd(r, y)，由于x小于y，所以k必然小于等于0。如果k等于0，那r等于x，你相当于没优化运算；如果k小于0，那么r反而比x大，恭喜你成功进行了反向“优化”。

为啥最后一个等式会是这种形式的呢？（r(n-1) = r(n)q(n)）

首先要明确，gcd(a, b) = gcd(|a|, |b|)，所以本算法中的参数均选择相应的绝对值，必为非负数。

回答分两种：

• 为什么不是r(n-1) = r(n)q(n) + r(n+1)呢？

因为如果此时余数r(n+1)不为0，则还要继续算下去，直到余数为0

• 为什么不是r(n-1) = r(n+1)，即 r(n)q(n)等于0呢？

答案很简单，如果r(n-1) = r(n+1)，即商q(n)为0，被除数等于余数。但是，余数r(n+1)是必须小于除数r(n)的，即可推导出r(n-1) = r(n+1) < r(n)。但是，我们很容易知道r(n-1)是必然大于r(n)的（因为r(n-1)是倒数第二个等式的除数，r(n)是倒数第二个等式的余数），产生矛盾，因此假设不成立。