费马小定理

若$p$是一个质数，而整数$a$不是$p$的倍数，则有$a^{p-1} \equiv 1(mod\; p)$。费马小定理是欧拉定理的一个特例。

欧拉定理

在数论中，欧拉定理(也称费马-欧拉定理)是一个关于同余性质的定理。实际上，它是费马小定理的推广。具体内容如下：

设$a,p$均是正整数，而且$gcd(a,p) = 1$,即$a,p$互质，那么我们有
$\qquad \qquad \qquad \qquad \qquad \qquad \qquad a^{\varphi(p)} \equiv 1(mod\;p)$

其中，$\varphi(m)$是$m$的欧拉函数。

与费马小定理的联系：当$p$是质数时，$\varphi(p) = p - 1$，欧拉定理退化为费马小定理。

裴蜀定理

在数论中，裴蜀定理是一个关于最大公约数的定理。

若$a,b$是整数，且它们的最大公约数是$d$,那么对于任意整数$x$和$y$,$ax+by$是$d$的倍数。特别地，一定存在整数$x$和$y$,使得$ax+by =d$成立。

中国剩余定理

中国剩余定理又称为孙子定理，它可用于求解一次同余线性方程组，是数论中的重要定理。

对于一个一元线性同余方程组
若整数$m_1,m_2,\cdots,m_n$中的任意两数互质，那么对于任意的整数$a_1,a_2,a_n$，一元线性同余方程组有解，并且同届可以通过如下方式构造得到：

设$M = m_1 \times m_2 \times \cdots \times m_n = \prod \limits_{i=1}^{n} m_i$是整数$m_1,m_2,\cdots,m_n$的乘积，并设$M_i = M / m_i,\forall i \in \{1,2,\cdots,n\}$，即$M_i$是除$m_i$以外$n-1$个数字的乘积。再设$t_i = M_i^{-1}$是$M_i$模$m_i$的乘法逆元：$t_i \times M_i \equiv 1(mod \;m_i),\forall i \in 1,2,\cdots,n$，那么方程组的通解为：$x = a_1t_1M_1 + a_2t_2M_2 + \cdots+a_nt_bM_n + kM = kM + \sum \limits_{i=1}^{n} a_it_iM_i,k \in \mathbb{Z}$ 。在模$M$的意义下，方程组只有一个解，$x = \sum \limits_{i=1}^{n} a_it_iM_i$。