欧拉函数与中国剩余定理

𝜙函数公式•如果p是素数，且𝑘≥1，则𝜙(𝑝𝑘)=𝑝𝑘−𝑝𝑘−1•如果𝑔𝑐𝑑(𝑚,𝑛)=1，则𝜙(𝑚𝑛)=𝜙(𝑚)𝜙(𝑛)证明瞪眼法可得证。中国剩余定理设𝑎1,𝑎2,…,𝑎𝑘是任意整数，且𝑛1,𝑛2,…,𝑛𝑘两两互素，则同余方程组{(𝑥≡𝑎1(mod𝑛1)𝑥≡𝑎2(mod𝑛2)…𝑥≡𝑎𝑘(mod𝑛𝑘))有解。令𝑁=∏𝑘𝑖=1𝑛𝑖，则同余方程组的解在模N下，唯一。唯一为：𝑥=(∑𝑘𝑖=1𝑎𝑖𝑁𝑛𝑖𝑚𝑖)mod𝑁其中𝑚𝑖为𝑁𝑛𝑖在模𝑛𝑖下的逆元