初等数论四大定理

在数论中，威尔逊定理、欧拉定理、孙子定理、费马小定理并称初等数论四大定理。

1. 威尔逊定理

如果整数 $p$ 满足 $(p-1)!\equiv-1\pmod p$ ，则 $p$ 是素数，逆定理同样正确。但是由于阶乘增长非常快的，其结论对于实际操作意义不大。
通俗点，当且仅当 $p$ 是素数，则 $(p-1)!+1$ 能被 $p$ 整除。

2. 欧拉定理

在数论中，欧拉定理（也称费马-欧拉定理）是一个关于同余的性质。
欧拉定理表明，若 $n,a$ 为正整数，且 $n,a$ 互质，则:
$a^{\varphi(n)}\equiv 1\pmod n$，
其中 $\varphi(n)$ 是欧拉函数：对于正整数 $n$，欧拉函数是不大于 $n$ 的正整数中与 $n$ 互质的数的数目。

3. 孙子定理

孙子定理是中国古代求解一次同余式组（见同余）的方法，是数论中一个重要定理，又称中国剩余定理。一元线性同余方程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下：
有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。

文献中描述的问题可以转化为一元线性同余方程组的求解：
$
f(x) =
\begin{cases}
x\equiv a_1\pmod{m_1} \
x\equiv a_2\pmod{m_2} \
\vdots \
x\equiv a_n\pmod{m_n} \
\end{cases}
$

当整数 $m1,m_2,\cdots,m_n$ 两两互质时，对于任意的整数 $a_1,a_2,\cdots,a_n$ 方程组 $f(x)$ 有解。求解方法如下：
设 $M=\prod{i=1}^n mi$ 是整数 $m_1,m_2,\cdots,m_n$ 的乘积，
$M_i=\frac{M}{m_i},i\in {1,2,\cdots,n}$ 是整数 $m_1,m_2,\cdots,m_n$ 中除了 $m_i$ 以外的 n-1 个整数的乘积，
$t_i=M_i^{-1},i\in{1,2,\cdots,n}$ 为 $M_i$ 模 $m_i$ 的数论倒数（$t_i$ 为 $M_i$ 模 $m_i$ 意义下的逆元），$M_it_i\equiv1\pmod {m_i}$。
方程组 $f(x)$ 的通解形式为 $x=M_1t_1a_1+M_2t_2a_2+\cdots+M_nt_na_n+kM=(\sum{i=1}^n Mit_ia_i )+kM, k\in Z$。
在模 $M$ 的意义下，方程组 $f(x)$ 只有一个解：$x=(\sum{i=1}^n M_it_ia_i)\bmod M$。

代码使用扩展欧几里得算法计算逆元，将 $f(x)$ 中的 $a_i,m_i$ 分别存入数组 a, m，下标从 1 开始。函数 crt() 返回 $x$。

const int MAXN = 100;
int a[MAXN], m[MAXN], n;
int exgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    int q = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return q;
}
int mod_inverse(int b, int mod)
{
    int x, y;
    exgcd(b, mod, x, y);
    return (mod + x % mod) % mod;
}
int crt(void)
{
    int M = 1, Mi, ti;
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        M *= m[i];
    for (int i = 1; i <= n; ++i)
    {
        Mi = M / m[i];
        ti = mod_inverse(Mi, m[i]);
        ans = (ans + Mi * ti * a[i]) % M;
    }
    if (ans < 0)
        ans += M;
    return ans;
}

4. 费马小定理

假如 $p$ 是素数，且 $gcd(a,p)=1$，那么 $a^{p-1}\equiv1\pmod p$。
例如：计算 $2^{100}$ 除以 $13$ 的余数。
$2^{100}\equiv 2^{12\times 8+4}\pmod {13}\equiv {2^{12}}^8\times 2^4\pmod {13}\equiv 1^8\times 16\pmod {13}\equiv 16\pmod {13}\equiv 3\pmod {13}$