模方程

• hxhu830 发布于
• 1686 收藏

不定方程 定义 给出一个方程ax+by=c，求x,y。 方法 不难发现，如果(a,b)不|c，肯定是无解的，因为ax+by是(a,b)的倍数，但是c不是(a,b)的倍数，所以ax+by≠c。 (a,b)|c时，我们会联想到这么一个方程： ax+by=(a,b) 这显然就是扩展欧几里得算法的经典问题，我们很容易就可以求出一组x,y。然后我们会发现x0=x*c/(a,b),y0=...