初等数论定理

中国剩余定理

对于线性同余方程组：

\(\begin{cases} x\equiv a_1 & \mod m_1 \\ x\equiv a_2 & \mod m_2 \\ \ldots \\ x\equiv a_n & \mod m_n \end{cases} \)

（\(m_1,m_2,\ldots,m_n\) 两两互质）

令 \(M=m_1 \times m_2 \times \ldots \times m_n\)

令 \(M_i=\dfrac{M}{m_i}\)

令 \(M_i^{-1}\) 表示 \(M_i \mod m_i\) 的逆元

则 \(x = a_1 \times M_1 \times M_1^{-1} + a_2 \times M_2 \times M_2^{-1} + \ldots + a_n \times M_n \times M_n^{-1}\)

欧拉定理

\(\gcd(a,n)=1 \;\; \Rightarrow \;\; a^{φ(n)} ≡ 1 (mod n)\)

\(φ(n)\) 表示小于 \(n\) 的正整数中与 \(n\) 互质的数的个数。

威尔逊定理

\(p∈prime \;\; \Leftrightarrow \;\; p\;|\;(p-1)! + 1\)

费马小定理

\(p ∈ prime\)

\(p \nmid a\)，则 $a^{p-1} ≡1 \mod p $

\(p \mid a\)，则 \(a^{p-1} ≡0 \mod p\)

裴蜀定理

设 \(a,b\) 是不全为零的整数，则存在整数 \(x,y\), 使 $ ax+by = \gcd(a,b)$。

在扩展欧几里得算法中，表现为 \(a,b\) 只要不都为零，则方程存在解。