可以和1构成扩展.
只要证明gcd(a,b),若b>a且b = am+r.
则有gcd(a,b) = gcd(a,r).
证明如下:
4.3 模运算:
同余:
同余类的引出.
(1) n|(a-b) 那么
这条经常被用来证明同余,因为整除理论里面有强大的(1)和(2),三角理论.
用符号来表示 模n的剩余类.
乘法逆元存在性的表征现象.
扩展euclid:
求解这样的:方程的.
而这样的方程是有扩展性的.
从而可以设k = qd.只要求解 的方程的解,若解为(x',y')那么方程的解就为(qx',qy').
从而问题在于求解算法很简单,只要基于以下两个原理:
那么b = 0的时候.d = gcd(a,0) = a,从而有解 (x=1,y = 0).