写给自己看，大佬们请移步，谢谢~
没有人可以请教真的是太痛苦了，大哭。
学了一天回到宿舍后，看了看刚发下来的课本，原来《信息安全数学基础》这门课学的就是初等数论，那我还自学干嘛。直接听老师讲吧。
本文基本不再更新，除非有些知识是课堂上不涉及的。
如有课堂笔记我会另开一贴。（flag已立）。说实话，除了韩老师的课之外，我很多专业课也大都是水下来的。忏悔一秒种。
推导中使用的是公因子，而不是最大公因子。
证明出整数r是a b的线性组合之后的一步，我的理解是这样的：
由带余除法的定义式可知，余数r必然满足0 <= r < d
注意，r是a b的线性组合，因为1 - qm和 -qm都是整数。既然是a b的线性组合，那自然也满足我们前面假设的d是ab的线性组合的最小的正整数这一条件。
所以r的最小正整数取值为d，但是不等式的右边又取不到等号，那就只能取0了。
一但r取0，就意味着前面的带余除法的等式中的余数为0，即d整除a.
即证R包含于S，且S包含于R.
由定理3.8，一定存在rs使得d = ra+sb（ab的最大公因子是ab的线性组合的最小正整数），所以有jd = jra + jsb。j是整数集内所有元素，但是jr和js未必能够遍历整数集，所以这里推出S是R的一部分，即S包含于R.
本定理较易理解，可概括为：两个不全为零的整数ab的最大公因子是能被其他所有的公因子整除的正公因子。
有几个点需要注意：
是正公因子。比如15和25的最大公因子是5，但是-5也是他俩的公因子，只不过是最小的。
如果某个公因子不能被另一个公因子整除，那么一定会有一个更大的公因子，即这二者的最小公倍数（我觉得哈。
按照这个原理，每次运算时，将较大的那个参数表示成带余除法的形式（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)不为0，则还要继续算下去，直到余数为0