同余 ●注意 ■并不是每个元素都有乘法逆元。 wEZn有逆元台gcdw,nF1 ■w是可逆的，则可以定义除法： ≡xw1modn Example ■设n=26,即Zn={1,2.,25},求15的加法、乘法逆元。 15+11≡0m0d26,15的加法逆元为11； gcd(15,26)=1且15×7≡mod26,15的乘法逆元为7
同余 注意 并不是每个元素都有乘法逆元。 w是可逆的，则可以定义除法： 𝒙 𝒘 ≡ 𝒙𝒘−𝟏𝐦𝐨𝐝 𝒏 Example 设n=26，即𝒁𝒏={1,2,…,25}，求15的加法、乘法逆元。 15+11 ≡0 mod 26，15的加法逆元为11； gcd(15,26)=1且15×7 ≡ mod 26，15的乘法逆元为7
同余 例 。求乘法逆元—欧几里得除法 ■设a,b是两个正整数，记r=a,r1=b,于是有： ro=q11+r2,0≤r2<1, r=q2'2+3,0≤3<r2, I-2=4-1'-tr1,0≤1<r-1, r-1=91 r-gcd(a,b)
同余 求乘法逆元——欧几里得除法 设a，b是两个正整数，记r0 = a，r1 = b，于是有： r0 =q1 r1+r2，0 r2 r1， r1 =q2 r2+r3，0 r3 r2， …… rl2 =ql1 rl1+rl，0 rl rl1， rl1 =ql rl． rl =gcd(a, b)
同余 。求乘法逆元—欧几里得除法 ■最大公因子定理：设，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的乘法逆元
同余 Example ■求15模26的逆元。 解： 26=1×15+11 1=4-1×3 15=1×11+4 =4-1×(11-2×4) =3×4-1×11 11=2×4+3 =3×(15-1×11)-1×11 4=1×3+1 =3×15-4×11 3=3×1 =3×15-4×(26-1×15) =7×15-4×26 所以15,26=1,15模26的逆元为7
同余 Example 求 15模26的逆元。 解： 26=115+11 15=111+4 11=24+3 4=13+1 3=31 所以(15, 26) =1, 15模26的逆元为7