如何求模方程解的个数？

Question

求 = x (mod m)

的解数

Answer 1

设p和q为质数。

如果因式互质，您可以将模方程分解为单独的方程。

这意味着**2 = x (mod m)等价于**2 = x (mod p)和**2 = x (mod q)。

这些中的每一个都可以因式分解为 x(x-1)=0 => x=0 or x=1。

所以你知道 x 是 0 或 1 模 p，x 是 0 或 1 模 q。根据中国余数定理，每个选项都有 1 个解模 m，所以将有 4 个解。

2 很容易（x=0 和 x=1）。另外两个可以用扩展欧几里德算法求得如下：

def egcd(a, b):
    x,y = 0,1
    lx,ly = 1,0
    while b != 0:
        q = a/b
        (a, b) = (b, a%b)
        (lx, x) = (x, lx-q*x)
        (ly, y) = (y, ly-q*y)        
    return (lx, ly)

p=7
q=11
m=p*q
(lx, ly) = egcd(p,q)
print lx*p%m,ly*q%m

如何求模方程解的个数？

How to find the number of solutions of modular equation?

modular-arithmetic