【数论】拓展欧几里得算法的多解

写在前面

　　这篇博客是我在【数论】对 算术基本定理 的研究 中的一部分

• 拓展欧几里得算法的多解

　　拓展欧几里得算法

　　求解得到的是一组p，q，是任意的一组p，q吗？

　　p，q肯定不止一对，那么如何获得多对p，q呢？

?

　　是否为任意的一组解先存疑

　　但能肯定的是，得到的不一定是最小整数解

?

　　想要求得多解也很容易：

　　　　∵p*a + q*b ==?gcd(a,b)

　　　　∴p*a + q*b + n*a*b - n*a*b ==?gcd(a,b)

　　　　∴(p + n*b)*a + (q - n*a)*b ==?gcd(a,b)

　　即任意一组解满足：

(p+n*b)，(q-n*a)

　　显然，对于任意的n∈Z都成立

　　利用这个性质就能求出所有解了！

此处p，q为利用拓展欧几里得算法得到的一组p，q

　　那么如何求得p或q的最小整数解呢？

　　其实同理，p%b就好了

　　但是p有可能为负数啊？

　　((p%b)+b)%b就好了