未完工。

目前咕掉的：

卢卡斯定理

~~真正有用的一个没有~~

质数：

威尔逊定理：$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 \]

JZTXT

关于一些初等数论的证明

未完工。

质数：

逆元：

组合数

欧拉函数

扩展欧几里得

中国剩余定理