Question

一道数论请找出一对整数x,y满足76x+45y=1

Answer 1

x=-29

y=49

用辗转相除法

y=(1-76x)/45=-x+(1-31x)/45

设y1=(1-31x)/45则45y1+31x=1

所以x=(1-45y1)/31=-y1+(1-14y1)/31

设x1=(1-14y1)/31则31x1+14y1=1

所以y1=(1-31x1)/14=-2x1+(1-3x1)/14

设y2=(1-3x1)/14则3x1+14y2=1

此时用观察法可知x1=-9 y2=2是一组解

再把结果代入上面的式子就行了.