UC知道裴蜀定理的证明
来源：百度知道 编辑：UC知道 时间：2024/06/16 15:02:00
就是整数a，b，（a，b）是他们的最大公约数，则一定存在整数x，y，使得ax+by=(a,b)
那么对于运用辗转相除法得到的那个解（x0，y0）可以用关于a，b或者（a，b）的代数式表示出来么？
那么对于运用辗转相除法得到的那个解（x0，y0）可以用关于a，b或者（a，b）的代数式表示出来么？
数论中有个结论
a=bq1+r1(0<r1<b)
b=r1q2+r2(0<r2<r1)
r1=r2q3+r3(0<r3<r2)
……
rk-2=rk-1qk+rk(0<rk<rk-1)
……
rn-2=rn-1qn+rn(0<rn<rn-1)
rn-1=rnqn+1
则(a,b)=(a-bq1,b)=(b,r1)=(r1,r2)=……=(rn-1,rn)=rn
设Q0=0,Q1=1,P0=1,P1=q1
Pk=qkPk-1+Pk-2
Qk=qkQk-1+Qk-2
(k>=2)
则aQk-bPk=(-1)^(k-1)rk,(k=1,2,……,n)