基础概念定义与性质
半群
- 定义：设\(S\)是一个具有结合法的非空集合，如果\(S\)满足结合律，那么\(S\)叫半群。
单位元、可逆元、逆元
- 性质1：设\(S\)是一个具有结合法的非空集合，则\(S\)中的单位元\(e\)是唯一的。
- 性质2：设\(S\)是一个具有单位元的半群，则对\(S\)中任意可逆元\(a\)，其逆元\(a'\)唯一。
群
定义1：设\(G\)是一个具有结合法的非空集合，如果这个结合法满足如下三个条件：
- 结合律：对任意\(a,b,c\in G\)，都有 \[(ab)c=a(bc)\]
- 单位元:存在一个元素\(e \in G\)，使得对任意\(a \in G\)，都有 \[ae=ea=a\]
- 可逆性：对任意的\(a \in G\)，都存在\(a‘ \in G\)，使得 \[aa'=a'a=e\] 那么，\(G\)叫做一个群。
定义2：若\(G\)是有单位元的半群，\(G\)中每个元都有逆元，则称\(G\)是一个群。 >- 定义1与定义2等价； >- 特别的，当\(G\)的结合法写作乘法时，\(G\)叫做乘群；当\(G\)的结合法写作加法时，\(G\)叫做加群。
定义3：群\(G\)的元素个数叫做群\(G\)的阶，记为\(|G|\)。当\(|G|\)为有限数时，\(G\)叫做有限群，否则\(G\)叫做无限群。
定义4：如果群\(G\)中的结合法还满足交换律，那么\(G\)叫做一个交换群或者阿贝尔群。
循环群
定义
设\(<\mathbb{G},*>\)是一个群，\(I\)是整数集合。如果\(\exist g\in \mathbb{G}\)，对\(\forall a \in \mathbb{G}\)，都有一个相应的\(i\in I\)，使得\(a = g^i\)，则称\(<\mathbb{G}, *>\)为循环群，\(g\)称为循环群得生成元，记\(\mathbb{G} = <g>=\{g^i|i\in I\}\)。称满足方程\(a^m = e\)的最小正整数\(m\)为\(a\)的阶，记为\(|a|\)。
环
定义1：设\(R\)是非空集合，“\(+\)”，“\(\cdot\)”是\(R\)的两个代数运算，如果
- \((R,+)\)是交换群；
- \((R,\cdot)\)是半群；
- \(\forall a,b,c\in R\), \[a\cdot (b+c)=(a\cdot b)+(a\cdot c)（左分配律）\] \[(a+b)\cdot c=(a\cdot c)+(b\cdot c)（右分配类）\] 则\(R\)称为环。
定义2：若\(\forall a,b \in R\)，有\(ab=ba\)，则\(R\)称为交换环。
定义3：若\(\forall a\in R\)，存在\(1_R\)，使得\(a1_R=1_Ra=a\)，则称\(R\)为有单位元环，也叫含幺环。
有限域
- 定义：设\(R\)为一个至少含2个元素的环，如果\(R\)中有单位元，且每个非零元都是可逆元，即\(R\)对于加法构成一个交换群，\(R^*=R\backslash \{0\}\)对于乘法构成一个群，则称\(R\)是一个除环。交换除环称为域。
素数（质数）
- 素数：称整数\(p(p>1)\)是素数，如果\(p\)的因子只有\(\pm 1\)和\(\pm p\)。
- 合数：若整数\(p(p>1)\)不是素数，则成为合数。
- 整数分解的唯一性：
任一整数\(a(a>1)\)都能被唯一地分解为以下形式： \[a=p_1^{a_1}p_2^{a_2}\cdots p_t^{a_t}\] 其中，\(p_1 < p_2 < \cdots < p_t\)，\(a_i > 0(i=1,\cdots ,t)\)。 > 任一正整数可由非0指数列表表示，例如11011可以表示为\(\{a_7 = 1, a_{11} = 2, a_{13} = 1\}\)。 - 最大公因子：如果
（1）\(c\)是\(a\)和\(b\)的公因子；
（2）\(a\)和\(b\)的任一公因子，也是\(c\)的因子。
则称\(c\)是\(a、b\)的最大公因子，表示为\(c = \gcd(a,b)\)。
>根据整数分解的唯一性，\(c\)可以表示为：\[c=p_1^{c_1}p_2^{c_2}\cdots p_t^{c_t}\]其中\(c_i=\min(a_i,b_i)，(i=1,\cdots ,t)\)。 - 互素数：如果\(\gcd(a,b)=1\)，称\(a\)和\(b\)互素。
- 最小公倍数：如果
（1）\(d\)是\(a\)和\(b\)的公倍数；
（2）\(a\)和\(b\)的任一公倍数，也是\(d\)的倍数。
则称\(d\)是\(a、b\)的最小公倍数，表示为\(d = \operatorname{lcm}(a,b)\).
>根据整数分解的唯一性，\(d\)可以表示为：\[d=p_1^{d_1}p_2^{d_2}\cdots p_t^{d_t}\]其中\(d_i=\max(a_i,b_i)，(i=1,\cdots ,t)\)。
> >特别的，如果\(a,b\)互素，则\(\operatorname{lcm}(a,b) = ab\)。
模运算
费尔马定理
定理
若\(p\)是素数，\(a\)是正整数且\(\gcd(a,p)=1\)，则\(a^{p-1}\equiv 1 \bmod{p}\)。
### 证明 由于\(\gcd(a,p) =
1\)，可知\(a \times \mathbb{Z_p} =
\mathbb{Z_p}\)。
又\(a \times 0 \equiv 0 \bmod
p\)，所以\(a \times (\mathbb{Z_p}
-\{0\}) = \mathbb{Z_p} -\{0\}\)。即
\[\{a\bmod p,2a \bmod p,\cdots , (p-1)a \bmod
p\} =\{1,2,\cdots, p-1\}\]
将左右两个集合中的元素分别连乘，可得 \[\begin{align*}
a\times 2a\times\cdots (p-1)a&\equiv[(a\bmod p)\times(2a \bmod
p)\cdots\times((p-1)a \bmod p)]\bmod p\\&\equiv(p-1)!\bmod p
\end{align*}\]
又\[a\times 2a\times\cdots
(p-1)a=(p-1)!a^{p-1}\]
所以
\[(p-1)!a^{p-1}\equiv (p-1)!\bmod
p\]
其中，\((p-1)!\)与\(p\)互质，因此\((p-1)!\)存在乘法逆元，由乘法可约律得
\[a^{p-1}\equiv 1\bmod p\]
欧拉定理
欧拉函数
设\(n\)是一正整数，小于\(n\)且与\(n\)互素的正整数的个数称为\(n\)的欧拉函数，记为\(\phi (n)\)。
定理
- （1）若\(n\)是素数，则\(\phi(n) = n - 1\)；
- （2）若\(n = p q\)，其中\(p,q\)都是素数，则\(\phi(n) = \phi(p)\phi(q)=(p-1)(q-1)\)； >若\(m,n\)互素，即\(\gcd(m,n) = 1\)，则\(\phi(mn) = \phi(m)\phi(n)\).（积性函数）
- （3）若\(n\)有标准分解式\(n = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_t^{\alpha_t}\)，则\(\phi(n) = \phi(p_1^{\alpha_1})\phi(p_2^{\alpha_2})\cdots \phi(p_t^{\alpha_t})=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots (1-\frac{1}{p_t})\)。
证明
关键证明两点：1、欧拉函数是积性函数；2、\(\phi(p^a) = p^a - p^{a-1}\)。
欧拉定理
定理
若\(a\)和\(n\)互素，则\(a^{\phi (n)} \equiv 1 \bmod n\)。
证明
首先证明：\(a\times R =
R\)，其中\(R = \{x_1, x_2,\cdots,
x_{\phi(n)}\}\)，
\(a \times R = \{ax_1 \bmod n, ax_2 \bmod n,
\cdots, ax_{\phi(n)} \bmod n\}\)，\(\forall x \in R, \gcd(x, n) = 1\)且\(x < n\)。
由模运算性质易得：\(\forall ax \bmod n\in a \times R, ax \bmod n < n\)；
\(\gcd(a,n) = 1； \forall x \in R, \gcd(x,n) = 1。\)所以，\(\forall ax \bmod n \in a \times R, gcd(ax, n) = 1\)；
首先假设存在$x_i,x_jR (ij)ax_i n = ax_j n， \(。由\)(a, n) = 1 b,ab n \(。若在\)ax_i n\(与\)ax_j n\(两侧同乘\)b\(，得\)x_i = x_j\(，矛盾，因此，\)x_i,x_j R(ij),ax_in ax_jn\(。从而，\)|a R| = |R|$。
由以上三点，可得\(a\times R = R\)。
之后证明：由\(a\times R = R\)得， \[\prod\limits_{i = 1}^{\phi(n)}(ax_i \bmod n) = \prod\limits_{i = 1}^{\phi (n)}x_i\] \[\prod\limits_{i = 1}^{\phi(n)}ax_i \equiv \prod\limits_{i = 1}^{\phi(n)}x_i \pmod{n} \Rightarrow a^{\phi(n)}\prod\limits_{i = 1}^{\phi(n)}x_i \equiv \prod\limits_{i = 1}^{\phi(n)} x_i \pmod{n}\] 由于\(\forall x \in R, \gcd(x,n) =1\)，可知\(\gcd(\prod\limits_{i = 1}^{\phi(n)}x_i,n) = 1\)，即\(\prod\limits_{i = 1}^{\phi(n)}x_i\)在\(\bmod n\)下有乘法逆元。故\(a^{\phi (n)} \equiv 1 \bmod n\)。
卡米歇尔定理
中国剩余定理
定理
设\(m_1,m_2,\cdots,m_k\)是两两互素的正整数，\(M=\prod\limits_{i=1}^km_i\)，则一次同余方程 \[\left\{ \begin{aligned} &a_1\pmod{m_1} \equiv x\\ &a_2\pmod{m_2} \equiv x\\ &\vdots\\ &a_k\pmod{m_k} \equiv x\\ \end{aligned} \right. \] 对模\(M\)有唯一解： \[x\equiv (\frac M{m_1}e_1a_1+\frac M{m_2}e_2a_2+\cdots +\frac M{m_k}e_ka_k)\pmod{M}\] 其中，\(e_i\)满足\(\frac M{e_i}\equiv1\pmod{m_i}(i = 1,2,\cdots,k)\)