同余 。求乘法逆元—欧几里得除法 ■最大公因子定理：设，b是两个不全为零的整数，则存在两个整数 u,y,使得 (a,b)=ua+yb ■求逆元 ■在欧几里得除法中，如果和n的最大公因子为1，通过反向迭代操 作有 ua+vn=(a,n)=1→ua三1modn ■u是a模n的乘法逆元。同余 求乘法逆元——欧几里得除法  最大公因子定理：设a，b是两个不全为零的整数，则存在两个整数 u，v，使得 (a, b)=ua+vb  求逆元  在欧几里得除法中，如果a和n的最大公因子为1，通过反向迭代操 作有 ua+vn=(a, n)=1 ⇒ ua≡1 mod n  u是a模n的乘法逆元