同余式：spa
设f(x)=an*(x**n)+an-1*(x**n-1)+...+a1*x+a0(n≥1,ai∈Z)，f(x)∈Z[x],则f(x)≡0 (modm)是模m的同余式，若an≠ 0(mod m),则f(x)≡0 (modm)的次数为n次co
（Cr是该同余式的解<==>f(r)≡0 (mod m)）
例：x**5+2x**4+x**3+2x**2-2x+3 ≡ 0 (mod 7)
当r=1时，则1+2+1+2-1+3=7≡0 (mod 7)
当r=2时，则2**5+2*2**4+2**3+2*2**2-2*2+3 =79 ≠ 0 （mod 79）
...
可求得，当r=1,5,6时，符合此同余式
定义：f(x1,x2,...,xk)∈Z[x1,x2,...,xk](k元整数系数多项式)，则
{Cr1,Cr2,...,Crk}是f(x1,x2,...,xk) ≡ 0(mod m)的解<==>f(r1,r2,...,rk) ≡ 0(mod m)(共有m**k种可能，且同余式的解是剩余类)
例：y**2-x**3+1≡0 (mod p)
当p=2时，{1,0}和{0,1}符合此同余式，即Np=2
当p=3时，{1,2}和{2,1},{2,2}符合此同余式，即Np=3
...
性质1：(a,m)=1,m≥1,则a*x≡b (mod m)恰有一解
证实：
C:{0,1,2,...,m-1}是模m的一组彻底剩余系
D:{a*0,a*1,...,a*m-1}也是模m的一组彻底剩余系
a*i ≡ <a*i> (mod m)
故∃i,有a*i ≡ b (mod m)
∴Ci是a*x≡b (mod m)的解（已证实有解）
假设a*i≡ b (mod m), a*j≡b(mod m)，其中i≠j
故a*i ≡ a*j (mod m)
∵(a,m)=1
∴i ≡ j (mod m)
∵i,j ∈{0,1,2,...,m-1},故i=j
又i≠j，故假设不成立，即只存在一个解（证实惟一性）
性质2：(a,m)=1,则C<a**((φ(m)-1)*b)>是a*x≡b (mod m)的惟一解
∵(a,m)=1
∴a**φ(m)≡1 (mod m)
故b*a**φ(m) ≡ b (mod m)
a*(a**(φ(m)-1)*b)≡ b (mod m)
即x ≡ a**(φ(m)-1)*b (mod m)
性质3：若(a,m)=d,则a*x≡ b(mod m)有解，当且仅当d | b
证实：
（必要性 有解-> d|b）
∵∃ x0,有a*x0 ≡ b (mod m)
∴∃ y0,有a*x0 = b +m*y0
∴a*x0-m*y0=b
又∵(a,m)|a,(a,m)|m
故(a,m)|b
即d|b
(充分性 d|b->有解)
a*x≡ b(mod m), d|b
故(a/d)*x ≡ b/d (mod m/d)
∵(a/d,m/d)=1,令a1=a/d,b1=b/d,m1=m1/d
则a1*x≡b1(mod m1)且（a1,m1）=1
故根绝性质1，此同余式且有一解x0
∴m/d | (a*x0-b)/d
即m | a*x0-b -->a*x0 ≡ b (mod m)
性质4：若(a,m)=d,d|b 则a*x≡b (mod m)恰有d个解(证实太难，之后补上！！！)
性质5：设k≥1,a1*x1+..+ak*xk ≡ 0 (mod m)有解，当且仅当(a1,a2,...,ak,m) | b ，设(a1,a2,...,ak)=d,若d|b则此同余式的解有(m**(k-1))*d个