扩展欧几里得算法求解模线性方程

• 秋思 发布于
• 1647 收藏

求解模线性方程组 求解线性不定方程组 ax + by = c 先求出一组解， 然后考虑如何表示通解， 设d = gcd(a, b), 假设c不是d的倍数， 则左边是d的倍数而右边不是， 则方程无解， 所以方程有解当且仅当d | c. 设c = c’ * d, 我们先考虑方程 ax + by = d, 这样由扩展gcd便可求出一组解 （x’, y’), 则（c’x’, c’y’)就是原...