ax ≡ 1 (mod b)与ax+by=gcd(a,b)有何关系?
问题描述:
ax ≡ 1 (mod b)与ax+by=gcd(a,b)有何关系?
答
前者说明gcd(a,b)=1,是后者的特殊情形
根据辗转相除法,总存在x,y满足后者