Блог пользователя Sayakiss

The root of ax+by=c given by Extended Euclidean algorithm is always smaller(or equal) than max(abs(a),abs(b))?
Автор Sayakiss, 13 лет назад, По-английски

void exgcd(int a,int b,int &x,int &y)

{
    if (b) {exgcd(b,a%b,y,x);y-=x*(a/b);}
    else x=1,y=0;
}
int main()
{
    int x,y;
    for(int i=1;i<=1000;i++)
    for(int j=i;j<=1000;j++)
    {
        exgcd(i,j,x,y);
        assert(max(abs(x),abs(y))<=max(i,j));
    }
}

this code ends without exception,that is to say,the root x,y equals or smaller than max(i,j) in [1..1000,1..1000].
I just wonder if it will hold for any i,j?
can anyone prove or disprove it?
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

This is pretty obvious. One may use induction to show that |x| ≤ |b| and |y| ≤ |a|. Step of induction is evident from straight check.
→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

可以得到abs(x)<=abs(b/d)  && abs(y)<=abs(a/d)
→ Ответить