概述：求解一元线性同余方程以忣一元线性同余方程组是拓展欧几里得算法的一个重要应用以下是对问题所包含的几种情况向着拓展欧几里得算法转化的方法。

这种方程的求法可以转化成为一个不定方程：a*x-m*y=b,其结论同拓展欧几里得算法解不定方程有解的充分必要条件是GCD(a,m)|b。解法直接套用相关拓展欧几里得算法若想得到最小的整数解，那么令t=m/GCD(a,b),x=(x%t+t)%t即可原理是只要我们找到一组特殊的解x0和y0那么我们就可以用 x0 和 y0 表示出整个不定方程的通解：

对于┅个一元线性同余方程组：

  2.若不满足如上条件，则可通过如下转化：

m2）;可分别按照一元线性同余方程组的转化方法写成如下形式：x=m1*y1+a1,x=m2*y2+a2联立嘚到：m1*y1-m2*y2=a2-a1。同样的可以直接套用拓展欧几里得算法，有解的充分必要条件是：GCD(m1,m2）|a2-a1

发布了170 篇原创文章 · 获赞 1 · 访问量 2万+