初等数论 裴蜀定理相关

题目

初等数论 裴蜀定理相关
怎么求ax+by=(a,b)的根?最好别用矩阵 要使用请介绍一些相关知识

答案

用辗转相除(欧几里得算法).
形式的描述比较麻烦,但是从例子很好理解.
比如a = 60,b = 86.
1) 带余除法b = a+26,余数c = 26;
2) 带余除法a = 2c+8,余数d = 8;
3) 带余除法c = 3d+2,余数e = 2;
4) 带余除法d = 4e,余数为0,这说明(a,b) = e = 2.
5) 逆推e = c-3d
= c-3(a-2c) = 7c-3a
= 7(b-a)-3a = 7b-10a.
因此x = -10,y = 7就是ax+by = e = (a,b)的一组解.
6) 写出通解x = b'k-10,y = 7-a'k,其中a' = a/(a,b),b' = b/(a,b).
即x = 43k-10,y = 7-30k.
简单总结就是辗转相除得到最大公约数,
再用过程中得到的等式逆推回去,得到用a,b表示(a,b)的等式,就找到一组解.
最后写出通解即可.