Sayakiss's blog

The root of ax+by=c given by Extended Euclidean algorithm is always smaller(or equal) than max(abs(a),abs(b))?
By Sayakiss, 13 years ago, In English

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?
  • Vote: I like it
  • 0
  • Vote: I do not like it

13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

This is pretty obvious. One may use induction to show that |x| ≤ |b| and |y| ≤ |a|. Step of induction is evident from straight check.
→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

可以得到abs(x)<=abs(b/d)  && abs(y)<=abs(a/d)
→ Reply