Bezout's identity Theorem 4( Bezout's Identity). If the greatest common divisor ofa and b is d, then d= arbs for some integers rand s 1876=365·5+511=3-2.1 365=517+8,2=8-3·2,=3-8-32=3 51=8·6+3 3=51-8.6 =351-8.6)-8=3.51-8.19 8=3·2+2, 8=365-51.7 =3:51-1935-57=136.51-19.365 3=2.1+1; 51=1876-365.5,=1361876-5-365-1951361876-69.365 Replace in the inverse direction 都 mfy@ustc.edu.cn 现代密码学理论与实践 24/55mfy@ustc.edu.cn 现代密码学理论与实践 24/55  Theorem 4 (Bezout’s Identity). If the greatest common divisor of a and b is d, then d = ar+bs for some integers r and s.  Replace in the inverse direction