设(a,b)=d,试证d是所有形如f(x,y)=ax+by的整数中最小正数,这里x,y为任意整数

问题描述:

设(a,b)=d,试证d是所有形如f(x,y)=ax+by的整数中最小正数,这里x,y为任意整数

首先由d | a与d |b,而x,y是整数,可知d | f(x,y).
故f(x,y)取得的最小正整数值 ≥ d.
只要再证明f(x,y)可以取得d.
这是裴蜀定理,即存在整数x,y使ax+by = (a,b) = d.
证明大致是用辗转相除,见参考链接.