设:
a 和 b 的最大公约数为w,
令
a = wc, b = wd, c,d互质
则
ax+by = t(aa+bb) ,t正整数
wcx+wdy = wwt(cc+dd)
cx+dy = wt(cc+dd)
令,
wt = v
则
cx+dy = v(cc+dd)
c(x-vc) = d(vd-y) 。。。。。。(式1)
因为,cd互质,
所以,
x-vc 可以被d整除
vd-y可以被c整除
令,
x-vc = p1*d
vd-y = p2*c
由式子1可以知道,p1=p2,令其为p
则:
x = vc+pd
y = dv-pc
xx = vvcc+ppdd+2vcpd
yy = ddvv+ppcc-2vcpd
xx+yy = vvcc+ppdd+ddvv+ppcc = (vv+pp)(cc+dd)
所以xx+yy有约数cc+dd,因为,c,d为正整数,所以,cc+dd>1
而
aa+bb = wcwc+wdwd=ww(cc+dd)
所以cc+dd也是aa+bb的约数,
所以xx+yy与aa+bb有公约数cc+dd


雷达卡



京公网安备 11010802022788号







