中国剩余定理求解同余方程又称孙子定理, 主要是为了解线同余方程组
在模M的意义下 x =
顯然带入方程组中可验证正确性,证明略
//非递归的扩展欧几里德算法
//求a相对于p的逆元，a、p互质才存在逆元
发布了110 篇原创文章 · 获赞 7 · 访问量 9萬+
中国剩余定理求解同余方程又称孙子定理, 主要是为了解线同余方程组
在模M的意义下 x =
顯然带入方程组中可验证正确性,证明略
//非递归的扩展欧几里德算法
//求a相对于p的逆元，a、p互质才存在逆元
发布了110 篇原创文章 · 获赞 7 · 访问量 9萬+
一次同余方程的求解步骤
用扩展歐几里得求解的具体做法如下：
对变形后的式子两边同时取模m得 ax'Ξd(mod)m至此可见x'是同余方程的解
然后根据上面的方法去解上面的题。代码是求得方程组小于m的非负整数解