2L

百度百科
一元线性方程组
X == a1 mod m1
...
X == an mod mn
mi互质
==============================================
设M = PI mi，Mi = M / mi，（mi 和 Mi 互质）， ti = Mi^-1（关于mi）
ai ti Mi == ai mod mi （ti Mi = 1 mod ）
ai ti Mi == 0 mod mj （i不等于j）
所以 x = sum ai ti Mi
又因为任意两个解 x1 - x2 = 0 mod mi （x1 == a1 mod m1，x2 == a1 mod m1 ...）
M 整除 x1 - x2
任意两个解之间差M
x = sum ai ti mi + kM

modular multiplicative inverse
find 3^-1, that is 3x3^1 == 1 mod 26
3 | 26 [ 26=8x3+2
3 | 2 [ 3=1x2+1
keep 3 and replace others
1 = 3 - 1 x 2
= 3 - 1 x (26 - 8 x 3) mod 26
= 3 - 26 + 8 x 3 mod 26
= 3 x 9 mod 26
So 3^-1=9

补充1
费马小定理
Fermat's little theorem
【1】p是一个质数，那么a^p-a是p的倍数，可以写成
a^p == a mod p
【2】如果a不能整除p，那么还可以的得到
a^(p-1) == 1 mod p

补充2
定义：d是模p的二次剩余 （quadratic residue modulo p） iff 存在完全平方数 x
d == x^2 mod p
##################
补充3
欧拉准则
Euler's Criterion
用来判断给定整数是否是模p的二次剩余 （p是质数）：
=> 对于整数d，（假设d不能整除p）
d是模p的 二次剩余iff d^(p-1 / 2) == 1 mod p ～～～～～～～～****
d是模p的非二次剩余iff d^(p-1 / 2) == -1 mod p
例子：
对于d=17，哪些质数p使得 d是模p的二次剩余？
p=13的时候 17 ^ (13-1 / 2) == 1 mod 13， 所以...
这个时候17 == 4 mod 13 ， 而4 = 2^2
###################
补充4
求解方程中x的解，其中p（质数）
=> x^2 == d mod p
结论：x1 == d^(p+1 / 4) mod p， x2 == p - x1
证明：把x1 带入原方程
d x d^(p-1 / 2) == d mod p 成立
（因为d是模p的二次剩余，必有 d^(p-1 / 2) == 1 mod p ）
x2 同样带入即可
######################
补充5
求解方程
=> z^2 == d mod p，其中p=mn（质数）
结论：现求解x^2 == d mod m 和 y^2 == d mod n得到
x1,x2, y1,y2
再求4组 同余方程组
x1 == z mod p
y1 == z mod q
-------------------
x1 == z mod p
y2 == z mod q
-------------------
x2 == z mod p
y1 == z mod q
-------------------
x2 == z mod p
y2 == z mod q
-------------------
over

ref
crt例子+二次剩余简单求解例子+d==z^2mod n(=pq)例子
www cs purdue edu/homes/ssw/cs555/new5 pdf