4.1 整除理论：
- b|g 且 b|h 对任意m,n 有 b|(mg+nh)。
2.整除三角理论： a|(b+c),a|b 则 a|c
可以和1构成扩展。
3.传递性：a|b , b|c 则 a|c。
4.2 Euclid算法：
只要证明gcd(a,b)，若b>a且b = am+r。
则有gcd(a,b) = gcd(a,r)。
证明如下：
4.3 模运算：
同余：
同余类的引出。
(1) n|(a-b) 那么
这条经常被用来证明同余，因为整除理论里面有强大的（1）和（2），三角理论。
用符号来表示 模n的剩余类。
乘法逆元存在性的表征现象。
扩展euclid：
求解这样的：方程的。
而这样的方程是有扩展性的。
ax+by = k
若上述方程有解，那么d|k。
因为k = ax+by，并且d|a并且d|b 所以d|k。
从而可以设k = qd.只要求解 的方程的解，若解为(x',y')那么方程
的解就为(qx',qy')。
从而问题在于求解
算法很简单，只要基于以下两个原理：
我们不影响答案地认为a>b。
那么
- b = 0的时候。d = gcd(a,0) = a,从而有解 (x=1,y = 0)。
2.方程和方程
同解。
证明：(x,y) = (x',y') 其中(x,y)为的解，(x',y')为
的解。
因为：
所以：
网友评论