未完工。
目前咕掉的：
卢卡斯定理
真正有用的一个没有
质数：
威尔逊定理：\(p\) 为质数的充要条件为 \((p-1)!\equiv -1\pmod p\)
证明：
\(1.\) 充分性：
反证，假设 \(p\) 是合数。
如果 \(p\) 为质数的平方，例如 \(p=4\)，则 \(3!\equiv 2\pmod 4\)，不成立。
令 \(p=k^2\)，因为 \(p>4\)，所以 \(k>2,2k<p,(p-1)!\equiv 0\pmod p\)
否则存在 \(p=ab,a\not = b\)，则 \((p-1)!\equiv nab\equiv 0\pmod p,n\in \N^+\)
\(2.\) 必要性：
若 \(p\) 是素数,取集合 \(A=\{1,2,3,\cdots.p -1\}\);
则 \(A\) 构成模 \(p\) 乘法的简化剩余系，即任意 \(i\in A\) ,存在 \(j\in A\)，使得：
$ij \equiv 1 \pmod p $ 那么 \(A\) 中的元素是不是恰好两两配对呢? 不一定,但只需考虑这种情况：
\(x^2 \equiv 1\pmod p\)
解得: \(x \equiv 1 \pmod p\) 或 \(x\equiv p - 1 \pmod p\)
其余两两配对，得 $( p - 1 )! \equiv (p-1) ≡ -1 \pmod p $
逆元：
定义：对于两个整数 \(x,p\)，若 \(xy\equiv 1\pmod p\) 时，则称 \(y\) 是 \(x\) 的逆元，记做 \(y=x^{-1}\)。
求法：当 \(p\) 是质数时，\(y\equiv x^{p-2}\pmod p\)。
由费马小定理可以得出，这里不再多说，可以参考 这篇题解。
这里的 \(y\) 可以使用快速幂计算，而快速幂这种简单的算法想必大家都会。
逆元满足以下几个性质：
- \([1,p)\) 的逆元互不相同。
证明：采用反证法，假设存在 \(x,y\)，满足 \(x\not= y\) 且 \(x,y\) 的逆元均为 \(i\)， \(xi\equiv yi\pmod p\)
两边同时除以 \(i\)，得出 \(x\equiv y\pmod p\)，矛盾。
- \(x\) 在以 \(p\) 为模数时存在逆元当且仅当 \(\gcd(x,p)=1\)。
证明：反证，设存在 \(x\) 的逆元，\(xx^{-1}\equiv1\pmod p\)
则 \(xx^{-1}=kp+1,k\in \Z\)。
设 \(d=\gcd(x,p)\)，则 \(\dfrac{xx^{-1}}{d}=\dfrac{kp+1}{d}\)
\(xx^{-1}\equiv 0\pmod d,kp+1\equiv 1\pmod d\)，矛盾。
于是同理可得推论 \([1,p)\) 中所有数存在逆元当且仅当 \(p\) 为质数。
- 线性求逆元
对于求 \(i\) 的逆元：
设 \(p=ki+r(0\le k,r<p)\)
\[k=\lfloor \dfrac{p}{i}\rfloor \]\[r=p-ki \]\[ki+r\equiv 0\pmod p \]同乘 \(i^{-1}r^{-1}\)，得 \(i^{-1}+k\times r^{-1}=0\)
\[i^{-1}\equiv -k\times r^{-1} \]组合数
\(C_n^m=\dfrac{n!}{m!(n-m)!}\)
引理：\(n\ge m\) 时，\(C_n^m=C_n^{n-m}\)。
可以根据定义入手得出。
卢卡斯定理的证明先咕了。
欧拉函数
令 \(\varphi(n)\) 表示 \(1,2,\cdots n\) 中与 \(n\) 互质的数。
性质 \(1\)：若 \(p\) 为质数，则 \(\varphi(p)=p-1\)。
废话。
性质 \(2\)：\(\varphi\) 是积性函数。
用 \([n]\) 表示 \(\{1,2,\dots, n\}(n>0)\)。设 \(n\) 有 \(k\) 个不同的质因子：\(p_1 < p_2 < \dots < p_k\)，由容斥原理有
\[\begin{aligned} \varphi(n) &= \sum_{I\subseteq [k]} (-1) ^{|I|} \frac{n}{\prod_{i\in I}p_i} \\ &= n\sum_{I\subseteq [k]} 1^{n - |I|} \prod_{i\in I} -\frac{1}{p_i} \\ &= n (1 - \frac1{p_1}) ( 1 - \frac1{p_2}) \dots (1 - \frac1{p_k}) \end{aligned}\]故得证。
性质 \(3\)：
\[\sum\limits_{d|n}\varphi(d)=n \]考虑 \(d\mid n\) 时，\(\sum\limits_{i=1}^n [\gcd(n,i)==d]=\varphi(d)\)
显然 \(\gcd(n,i)\mid n\)
所以 \(\sum\limits_{d|n}\sum\limits_{i=1}^n [\gcd(n,i)==d]=n\)。
于是 \(\sum\limits_{d|n}\varphi(d)=n\) 成立。
欧拉定理：
\[a^{\varphi(p)}\equiv 1\pmod p \]证明：
取模 \(p\) 的缩系 \(a_1,a_2\cdots a_{\varphi(p)}\)，则 \(aa_1,aa_2\cdots aa_{\varphi(p)}\) 也为模 \(p\) 的缩系。
于是
\[\prod\limits_{i=1}^{\varphi(p)}a_i\equiv \prod\limits_{i=1}^{\varphi(p)}\pmod p \]得出结论：
\[a^{\varphi(m)}\equiv 1\pmod p \]当 \(p\) 为质数时，该定理退化成费马小定理。
\[a^{p-1}\equiv 1\pmod p \]于是费马小定理就不证了。
扩展欧几里得
\(1.\) 裴蜀定理：
\(ax+by=c\) 的充要条件为 \(\gcd(a,b)\mid c\)
证明：
\(1.\) 必要性：
令 \(d=\gcd(a,b)\)，显然 \(d\mid a,d\mid b\)，因为 \(x,y\in \N^+\)，所以 \(d\mid ax,d\mid by,d\mid c\)，得证。
充分性：由扩展欧几里得算法必然可以构造出 \(ax+by=c\) 的解
中国剩余定理
给定 \(n\) 组非负整数 \(a_i, b_i\) ，求解关于 \(x\) 的方程组的最小非负整数解。
\[\begin{cases} x\equiv a_1\pmod {m_1} \\ x\equiv a_2\pmod {m_2} \\ \cdots \\ x \equiv a_n\ \pmod {m_n}\end{cases} \]中国剩余定理：
令 \(M=\prod\limits_{i=1}^{n}m_i\bmod p,M_i=\dfrac{M}{m_i}\)
设 \(t_i\) 为 \(M_i\) 以 \(m_i\) 为模数的逆元，即 \(t_iM_i\equiv 1\pmod {m_i}\)
则 \(x\) 的最小非负整数解为
\[x=\sum\limits_{i=1}^{n}a_it_iMi\bmod p \]证明：
由假设可知，对于所有 \(i\in\{1,2,\cdots n\}\)，由于 \(\forall j\in\{1,2,\cdots n\},j\not =i,\gcd(m_i,m_j)=1\)，所以可得 \(\gcd(m_i,M_i)=1\)，所以必然存在 \(t_i\)，满足 \(t_iM_i\equiv 1 \pmod {m_i}\)。
再看一下这个式子：
\[a_it_iM_i \]不难发现，\(t_iM_i\equiv 1\pmod p\)，所以 \(a_it_iM_i\equiv a_i\pmod {m_i}\)。
\[\forall j\in\{1,2,\cdots n\},j\not =i,a_it_iM_i\equiv 0\pmod {m_j} \]所以 \(x=\sum\limits_{i=1}^{n}a_it_iMi\bmod p\) 满足 \(\forall i\in\{1,2,\cdots n\},x\equiv a_it_iM_i+\sum\limits_{j\not=i}a_jt_jM_j\equiv a_i\pmod {m_i}\)
若 \(x_1,x_2\) 均为方程的解，显然 \(x_1\equiv x_2\pmod M\)。
于是解集为
\[\{kM+\sum\limits_{i=1}^{n}a_iy_iM_i\},k\in \Z \] 标签：limits,数论,sum,varphi,证明,pmod,逆元,初等,equiv From： https://www.cnblogs.com/Stitch0711/p/17436666.html