ax ≡ 1 (mod b)与ax+by=gcd(a,b)有何关系?

问题描述:

ax ≡ 1 (mod b)与ax+by=gcd(a,b)有何关系?

前者说明gcd(a,b)=1,是后者的特殊情形
根据辗转相除法,总存在x,y满足后者