初等数论第三版,第二节习题2答案证明(a,b)=a*x0+b*y0,其中a*x0+b*y0是形如a*x+b*y(x,y是任意整数)的整数里的最小,并将此推广到n个整数的情形

Question

初等数论第三版,第二节习题2答案
证明(a,b)=a*x0+b*y0,其中a*x0+b*y0是形如a*x+b*y(x,y是任意整数)的整数里的最小,并将此推广到n个整数的情形

Answer 1

记d=(a,b)
d|a 且 d|b
所以对任意整数 x, y,有：d | (ax+by)
也就是对任意整数 x, y,都存在整数 k,使得：kd = ax+by
所以,除非 k=0 （此时 ax+by=0）,否则 k=1 或 -1 就是所有 ax+by 中绝对值最小的那个.
将其推广到 n：
d = (a1, a2, ..., an)
则对于任意整数 x1, x2, ..., xn,有：d | (a1x1+a2x2+...+anxn)
所以,d 是所有 a1x1+a2x2+...+anxn 中绝对值最小且不等于0的那个.