数论知识点整理
提前感谢 某同学的友情帮助
由于之前的知识不是很难，所以从同余开始整理
同余
定义
Def 1.1
设 \(m \in \mathbb{Z}_{>0} , m \mid a-b\),称\(a\)与\(b\)关于模\(m\)同余。记作
\[a \equiv b \pmod m\]
否则称\(a\)与\(b\)不同余，记作\(a \not\equiv b\)
同余的性质： 自反性，对称性，传递性
Statement 1.2
若 \((a,m)=1\), 则存在\(a'\) 使得\(a \cdot a' \equiv 1 \pmod m\), 我们称\(a'\) 为 \(a\) 在模\(m\)下的逆元，记作\(a^{-1}\)或\(\bar{a}\)
关于同余还有一部分显然的性质，这里暂时不列出来。有兴趣的同学可以自己参考
剩余类与剩余系
Def 2.1
给定模\(m\), 对任意的整数\(r\), 把与\(r\)同余的整数的集合称为模\(m\)的一个剩余类，记作\(r \mod m ={r+km : k \in \mathbb{Z}}\)
容易发现不同的剩余类互不相交。
Def 2.2
若\(a_1 ,\cdots ,a_m\)是两两模\(m\)不同余的整数，则称\(\{ a_1 ,\cdots ,a_m \}\)是模\(m\)的一个完全剩余系。
Def 2.3
若\((r,m)=1\)，则称\(r\mod m\)为模\(m\)的一个既约剩余类。
Def 2.4
模\(m\)的全部既约剩余系为
\[r \mod m, ~ 1\leq r \leq m, ~ (r,m)=1\]
我们把模\(m\)的所有既约剩余类的个数记作\(\varphi (m)\)，并称\(\varphi (m)\)为模\(m\)的欧拉函数。
Def 2.5
从模\(m\) 的每个既约剩余类中各取一个元素所形成的集合被称作模\(m\)的一个简化剩余系。且这个集合有\(\varphi(m)\)个元素。
Theorem 2.6
设 \(n \in \mathbb{Z}_{\geq 1}\), 则
\[\sum_{d\mid n} \varphi(d)=n\]
定理的含义即为: \(n\)的所有正因子\(d\)的欧拉函数之和为\(n\).
Proof 2.6 我们把区间 \([1,n]\) 中的数按照和\(n\)的最大公因数来分类，即
\[n = \sum_{k \leq n}1 = \sum_{d\mid n} \sum_{k \leq n \atop (k,n)=d}1= \sum_{d \mid n} \sum_{k \leq n/d\atop (k,n/d)=1}1 = \sum_{d\mid n } \varphi (\frac{n}{d})= \sum_{d\mid n} \varphi(d)\]
Remark 2.6 这里的证明实际上是运用了计数函数，并把计数函数分类后重排得到的结果
Theorem 2.7 设 \((a,m)=1 , b \in \mathbb{Z}\)
- \(\{ x_1 , \cdots x_m \}\) 是模\(m\)的一个完全剩余系,则 \(\{ ax_1+b , \cdots ax_m +b\}\) 是模\(m\)的一个完全剩余系。
- \(\{x_1,\cdots,x_{\psi(m)}\}\)是模\(m\)的一个简化剩余系,则\(\{ax_1,\cdots,ax_{\psi(m)}\}\)是模\(m\)的一个简化剩余系。
Remark 2.7 如果要证明一个集合是模 \(m\) 的完全剩余系，则要证明这个集合中的任意两个元素都不同余，且个数为 \(m\) 。而如果要证明一个集合是模\(m\)的简化剩余系，则要证明这个集合中的任意两个元素都不同余，且这个集合中的元素个数为\(\varphi(m)\)，每个集合的 \(r\) 和 \(m\) 均互素。
Remark 2.7.2 上述定理可以由一个更推广的结论表示，为：
设\(M =mn,(m,n)=1,\)记
\[ z_{ij}= nx_i+ my_j \quad 1\leq i \leq s; ~1\leq j \leq t\]
则 \(z_{ij}\) 构成模\(M\)的完全（简化）剩余系当且仅当 \(x_i\)构成模\(m\)的完全（简化）剩余系，\(y_j\)构成一个模\(n\)的完全(简化)剩余系。
Statement 2.8 由上述命题，我们可以得到以下推论：
若 \(m,n \in \mathbb{Z} _{>0}\) 且 \(m,n\) 互素，则 \(\varphi(mn)=\varphi(m) \varphi(n)\) 。
Remark 2.9 上述命题表明欧拉函数\(\varphi(n)\)是一个积性函数。并由此可以给出关于\(\varphi(n)\)的一个计算公式。
Theorem 2.10 设 \(n \in \mathbb{Z}_{>0}\), 则
\[\varphi(n)=\prod_{p\mid n} (1-\frac{1}{p})\]
Proof 2.10 由欧拉函数的定义可知，\(\varphi(n)\)是\(n\)的所有正因子\(d\)的欧拉函数之和，即
\(n=1\)显然成立，对于 \(n>1\)，设\(n\)的标准分解式为\(n=p_1^{\alpha_1}\cdots p_r^{\alpha_r}\)。而欧拉函数是可积的，于是
\[\varphi(n)=\varphi(p_1^{\alpha_1})\cdots \varphi(p_r^{\alpha_r})\]
由于
\[\varphi(p^\alpha)=\sum_{(k,p)=1\atop k =1}^{p^\alpha}1=\sum_{k=1}^{p^\alpha}1-\sum_{p\mid k \atop k=1 }^{p^\alpha}1 =p^\alpha-p^{\alpha-1}=p^\alpha(1-\frac{1}{p})\]
欧拉定理
Theorem 3.1 设\(m\)是正整数，\((a,m)=1,\) 则 \(a^{\varphi(m)}\equiv 1 \pmod m\)
Remark 3.1 由欧拉定理，我们可以很轻易的证明费马小定理。
Theorem 3.2 设 \(p\) 是素数，\(a\) 是整数，且 \(a \not \equiv 0 \pmod p\)，则 \(a^{p-1}\equiv 1 \pmod p\)
Proof 3.2 由欧拉定理可知，\(a^{\varphi(p)}\equiv 1 \pmod p\)，而 \(\varphi(p)=p-1\)，所以 \(a^{p-1}\equiv 1 \pmod p\)
同余方程
一次同余方程
Def 1.1 设 \(f(x)=a_nx^n+ \cdots +a_1x+a_0\) 为整系数多项式，\(m\) 是正整数，若存在整数 \(k\) 使得 \(f(k)\equiv 0 \pmod m\)，则称 \(x\equiv k\pmod m\) 为方程 \(f(x)\equiv 0 \pmod m\) 的一个解。
Theorem 1.2 记 \(d=(a,m),\) 则同余方程
\[ax\equiv b \pmod m\]
有解当且仅当 \(d|b\)。且方程的全部解为
\[x \equiv x_0 + \dfrac{m}{d}k \pmod m \quad k=0,1,\cdots ,d-1\]
其中 \(x_0 \pmod m\) 是方程的一个特解。且方程的全部解可以由
\[\left\{ \begin{aligned} & x =x_0 +\frac{m}{d} k\\ & y =y_0 - \frac{a}{d}k \end{aligned} \quad (k \in \mathbb{Z})\right. \]
Theorem 1.3 由上面的命题，我们可以很容易得到以下推论：
若 \((a,m)=1,\) 则同余方程 \(ax\equiv b \pmod m\) 有唯一解。
Theorem 1.4 设 \(m_1, \cdots m_k\) 是两两互素的正整数，并记 \(m=m_1\cdots m_k\)，则同余方程
\[f(x) \equiv 0 \pmod m\]
与同余方程组
\[\left\{ \begin{aligned} & f(x)\equiv 0 \pmod {m_1} \\ & f(x)\equiv 0 \pmod {m_2} \\& ……………… \\ & f(x)\equiv 0 \pmod {m_k} \end{aligned} \right.\]
等价。
中国剩余定理
Theorem 2.1 (中国剩余定理) 设 \(m_1 \cdots m_k\) 是两两互素的正整数，并记 \(m=m_1\cdots m_k\)，则同余方程组
\[\left\{ \begin{aligned} & x\equiv a_1 \pmod {m_1} \\ & x\equiv a_2 \pmod {m_2} \\& ……………… \\ & x\equiv a_k \pmod {m_k} \end{aligned} \right.\]
对模 \(m\) 有唯一解。
Proof 2.1 存在性：记\(M_j =\dfrac{m}{m_j}\)，则记\(\overline{M_j}\) 为满足\(\overline{M_j}M_j \equiv 1 \pmod {m_j}\) 的整数，因为对任意的 \(l\) 有
\[\sum_{j=1}^k a_j \overline{M_j}M_j \equiv a_l \overline{M_l}M_l \equiv a_l \pmod {m_l}\]
于是
\[x\equiv \sum_{j=1}^k a_j \overline{M_j}M_j \pmod m\]
是方程的一个解。
Remark 2.1 中国剩余定理是非常重要的一个定理。