欧拉函数与中国剩余定理

函数公式

• 如果p是素数，且，则

• 如果，则

证明

瞪眼法可得证。

中国剩余定理

设是任意整数，且两两互素，则同余方程组

有解。令，则同余方程组的解在模N下，唯一。

唯一为：

其中为在模下的逆元