1.7拓展阅读：从星期到模m剩余类环
本页由讲义拆分版 TeX 初步转换生成；答案默认收起。
讲义正文
拓展阅读：从星期到模\(\displaystyle m\)剩余类环
集合的划分与等价关系
看2010年3月份的日历：
| {ccccccc}
日 | 一 | 二 | 三 | 四 | 五 | 六 |
| --- | --- | --- | --- | --- | --- | --- |
| | 1 | 2 | 3 | 4 | 5 | 6 |
| 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| 21 | 22 | 23 | 24 | 25 | 26 | 27 |
| 28 | 29 | 30 | 31 | | | |
显然,“星期一”是由无穷多天组成的集合,“星期二”、……、“星期日”同理.
如何表示星期一这个集合呢？我们想到描述法,那么属于星期一的那些日子的特征是什么呢？为简化问题,我们将2010 年 3 月 1 日对应到数1,3 月 2 日对应到 2,\(\displaystyle \cdots\),3 月 31 日对应到 31,……；把 2010 年 2 月 28 日对应到 0,2 月 27 日对应到 \(\displaystyle -1, 2\) 月 26 日对应到 \(\displaystyle -2, \cdots\).这个对应法则是时间长河中的所有日子组成的集合到整数集 \(\displaystyle \mathbb{Z}\) 的一个双射.
可以看出,星期日是由被 7 除后余数为 0 的整数组成的集合,星期一是由被 7 除后余数为 1 的整数组成的集合,\(\displaystyle \cdots\),星期六是由被 7 除后余数为 6 的整数组成的集合,把这些子集依次记为 \(\displaystyle H_0,H_1, H_2, \dots, H_6\)：
$$\displaystyle H_0 &= {7k \mid k \in \mathbb{Z}},
H_1 &= {7k+1 \mid k \in \mathbb{Z}},
H_2 &= {7k+2 \mid k \in \mathbb{Z}},
&\dots \dots \dots
H_6 &= {7k+6 \mid k \in \mathbb{Z}}.
$$
于是 \(\displaystyle \mathbb{Z}\) 被分成了 7 个子集,且满足
$\(\displaystyle \mathbb{Z} = H_1 \cup H_2 \cup H_3 \cup H_4 \cup H_5 \cup H_6 \cup H_0, \text{ 当 } i \neq j\text{时},\ H_i \cap H_j = \varnothing\)$
从这个例子抽象出下述概念：
定义 1.7.1（集合的划分）
如果集合 \(\displaystyle S\) 是它的一些非空子集的并集,其中每两个不相等的子集的交为空集（此时称它们不相交）,那么把这些子集组成的集合称为 \(\displaystyle S\) 的一个划分.
在上述例子中,\(\displaystyle \{H_0,H_1, H_2, H_3, H_4, H_5, H_6\}\) 是整数集 \(\displaystyle \mathbb{Z}\) 的一个划分.
我们自然要问,如何给出任一集合 \(\displaystyle S\)的一个划分呢？
对于上述例子，两个整数 \(\displaystyle a,b\) 属于同一个子集当且仅当它们模7同余。
任给两个整数 \(\displaystyle a\) 与 \(\displaystyle b\),要么 \(\displaystyle a\) 与 \(\displaystyle b\) 模 7 同余,要么 \(\displaystyle a\) 与 \(\displaystyle b\) 模 7 不同余,二者必居其一且只居其一.自然地，可以把模 7 同余称为整数集 \(\displaystyle \mathbb{Z}\) 上的一个二元关系.
在数学上如何给出集合 \(\displaystyle S\) 的二元关系的定义呢？以 \(\displaystyle \vv{Z}\) 上的模 7 同余关系为例,既然要考察任意两个整数有没有这个关系,自然要考虑所有有序整数对\(\displaystyle (a,b)\)组成的集合\(\displaystyle \mathbb{Z}\times \mathbb{Z}\),可知有下述结论：
$\(\displaystyle a \equiv b (\bmod 7) \iff (a, b) \in \bigcup_{i=0}^6 H_i \times H_i,\)$
\(\displaystyle \bigcup_{i=0}^6 H_i \times H_i\) 是 \(\displaystyle \mathbb{Z} \times \mathbb{Z}\) 的一个子集,\(\displaystyle (a,b)\) 属于这个子集就表明 \(\displaystyle a\) 与 \(\displaystyle b\) 有模 7 同余关系,否则表明 \(\displaystyle a\) 与 \(\displaystyle b\) 没有模 7 同余关系.我们干脆就把 集合\(\displaystyle \bigcup_{i=0}^6 H_i \times H_i\) 叫做 \(\displaystyle \mathbb{Z}\) 上的模 7 同余关系.由此抽象出下述概念：
定义 1.7.2（二元关系）
设 \(\displaystyle S\) 是一个非空集合,把 \(\displaystyle S \times S\) 的非空子集 \(\displaystyle W\) 称为 \(\displaystyle S\) 上的一个二元关系.如果 \(\displaystyle (a, b) \in W\),那么称 \(\displaystyle a\) 与 \(\displaystyle b\) 有 \(\displaystyle W\) 关系,记做 \(\displaystyle a W b\)或\(\displaystyle a \sim b\),否则称 \(\displaystyle a\) 与 \(\displaystyle b\) 没有 \(\displaystyle W\) 关系.
\(\displaystyle \mathbb{Z}\) 上的模 7 同余关系具有下述性质：
（1）\(\displaystyle \forall a \in \mathbb{Z},a \equiv a (\bmod 7)\)；
（2）若 \(\displaystyle a \equiv b (\bmod 7)\),则 \(\displaystyle b \equiv a (\bmod 7)\)；
（3）若 \(\displaystyle a \equiv b (\bmod 7)\) 且 \(\displaystyle b \equiv c (\bmod 7)\),则 \(\displaystyle a \equiv c (\bmod 7)\).
由此引出下述概念：
定义 1.7.3（等价关系）
集合 \(\displaystyle S\) 上的一个二元关系\(\displaystyle \sim\) 如果具有下列性质：
\(\displaystyle 1^\circ: \ a \sim a, \forall a \in S\)（自反性/反身性）；
\(\displaystyle 2^\circ:\) 若 \(\displaystyle a \sim b\),则 \(\displaystyle b \sim a\)（对称性）；
\(\displaystyle 3^\circ:\) 若 \(\displaystyle a \sim b\) 且 \(\displaystyle b \sim c\),则 \(\displaystyle a \sim c\)（传递性）,
那么称\(\displaystyle \sim\) 是 \(\displaystyle S\) 上的一个等价关系.
\(\displaystyle \mathbb{Z}\) 上的模 7 同余关系就是 \(\displaystyle \mathbb{Z}\) 上的一个等价关系.
我们还能观察到：星期一就是由与 1 模 7 同余的整数组成的子集,\(\displaystyle \cdots\),星期日是由与 0 模 7 同余的整数组成的子集.由此受到启发,引出下述概念：
定义 1.7.4（等价类）
设\(\displaystyle \sim\)是集合 \(\displaystyle S\) 上的一个等价关系,对于 \(\displaystyle a \in S\),集合\(\displaystyle \{x \in S \mid x \sim a\}\)称为由 \(\displaystyle a\) 确定的等价类,记做 \(\displaystyle \overline{a}\).
星期一、……、星期六、星期日就是 \(\displaystyle \mathbb{Z}\) 在模 7 同余关系下的 7 个等价类：
$\(\displaystyle \overline{0} = \{x \in \mathbb{Z} \mid x \equiv 0(\bmod 7)\} = \{7k \mid k \in \mathbb{Z}\}.\)$
$\(\displaystyle \overline{1} = \{x \in \mathbb{Z} \mid x \equiv 1(\bmod 7)\} = \{7k+1 \mid k \in \mathbb{Z}\},\)$
$\(\displaystyle \dots \dots \dots \dots \dots \dots \dots\)$
$\(\displaystyle \overline{6} = \{x \in \mathbb{Z} \mid x \equiv 6(\bmod 7)\} = \{7k+6 \mid k \in \mathbb{Z}\},\)$
这 7 个等价类都叫做模 7 剩余类.
下面我们来探索等价类的性质.设\(\displaystyle \sim\)是集合 \(\displaystyle S\) 上的一个等价关系.
性质 1： \(\displaystyle a \in \overline{a}, \forall a \in S.\)
由于性质 1,可以把 \(\displaystyle a\) 称为等价类 \(\displaystyle \overline{a}\) 的一个代表.
性质 2： \(\displaystyle x \in \overline{a} \iff x \sim a.\)
性质 3： \(\displaystyle \overline{x} = \overline{y} \iff x \sim y.\)
由性质 2 和性质 3 得,若 \(\displaystyle x \in \overline{a}\),则 \(\displaystyle x \sim a\),从而 \(\displaystyle \overline{x} = \overline{a}\).这表明 \(\displaystyle \overline{a}\) 中任一元素 \(\displaystyle x\) 都可以作为等价类 \(\displaystyle \overline{a}\) 的代表.
性质 4： 任给 \(\displaystyle a, b \in S\),则 \(\displaystyle \overline{a}\) 与 \(\displaystyle \overline{b}\) 或者相等,或者不相交.
由性质 4 可以发现下述定理：
定理 1 设\(\displaystyle \sim\)是集合 \(\displaystyle S\) 上的一个等价关系,则所有等价类组成的集合是 \(\displaystyle S\) 的一个划分.
我们从星期一、……、星期六、星期日引出了等价类的概念.通过探索等价类的性质,发现并证明了定理 1.这是数学思维方式的一个体现.定理 1 给出了集合划分的一个统一的常用的方法,即在集合 \(\displaystyle S\) 上建立一个二元关系,验证它是否为等价关系,如果是等价关系,那么所有等价类组成的集合是 \(\displaystyle S\) 的一个划分.反之,如果给了集合 \(\displaystyle S\) 的一个划分,那么可以在 \(\displaystyle S\) 上建立一个等价关系,使得 \(\displaystyle S\) 的这个划分就是由所有等价类组成的.
与模 7 同余关系类似,给定 \(\displaystyle m\in \mathbb{Z},m>1\),可以在整数集 \(\displaystyle \mathbb{Z}\) 上建立一个模 \(\displaystyle m\) 同余关系：
\[\displaystyle a \equiv b (\bmod m) \iff a-b \text{ 是 } m \text{ 的整数倍}. \quad \quad \quad\]
显然,这是 \(\displaystyle \mathbb{Z}\) 上的一个等价关系.共有 \(\displaystyle m\) 个等价类：
\[\displaystyle \overline{0} = \{x \in \mathbb{Z} \mid x \equiv 0 (\bmod m)\} = \{km \mid k \in \mathbb{Z}\},$$
$$\displaystyle \overline{1} = \{x \in \mathbb{Z} \mid x \equiv 1 (\bmod m)\} = \{km+1 \mid k \in \mathbb{Z}\},$$
$$\displaystyle \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots$$
$$\displaystyle \overline{m-1} = \{x \in \mathbb{Z} \mid x \equiv m-1 (\bmod m)\} = \{km+(m-1) \mid k \in \mathbb{Z}\},\]
它们都称为模 \(\displaystyle m\) 剩余类.集合
$\(\displaystyle \{\overline{0}, \overline{1}, \dots, \overline{m-1}\}\)$
是 \(\displaystyle \mathbb{Z}\) 的一个划分,把这个集合记做 \(\displaystyle \mathbb{Z}_m\).
观察：\(\displaystyle 23 \equiv 2(\bmod 7), 10 \equiv 3(\bmod 7)\),
$\(\displaystyle 23+10 \equiv 2+3(\bmod 7), \quad 23 \times 10 \equiv 2 \times 3 (\bmod 7).\)$
由此受到启发,猜测模 \(\displaystyle m\) 同余关系有下述性质：
\paragraph{命题 1} 设 \(\displaystyle m\) 是大于 1 的整数.若\(\displaystyle a \equiv b(\bmod m) \text{且} c \equiv d(\bmod m)\),那么 \(\displaystyle a+c \equiv b+d(\bmod m)\)且 \(\displaystyle ac \equiv bd(\bmod m)\).
从命题 1 立即得到：若 \(\displaystyle a \equiv b(\bmod m)\),则对任意整数 \(\displaystyle c\) 有 \(\displaystyle ca \equiv cb(\bmod m)\).
- 在平面点集 \(\displaystyle S\)上定义一个二元关系：
$\(\displaystyle P_1(x_1, y_1) \sim P_2(x_2, y_2) \iff x_1-x_2 \in \mathbb{Z} \text{ 且 } y_1-y_2 \in \mathbb{Z}.\)$
证明：\(\displaystyle \sim\) 是 \(\displaystyle S\) 上的一个等价关系.
- 证明或反驳：若 \(\displaystyle ca \equiv cb(\bmod 6)\),则 \(\displaystyle a \equiv b(\bmod 6)\).
模 \(\displaystyle m\) 剩余类环 \(\displaystyle \mathbb{Z}_m\), 环和域的概念
假设今天是星期五,过了 181 天是星期几？由于每过 7 天又是星期五,\(\displaystyle 181 \equiv 6(\bmod 7)\),\(\displaystyle 5+6 \equiv 4(\bmod 7)\),因此过了 181 天是星期四.
星期五是 \(\displaystyle \mathbb{Z}\) 的一个子集 \(\displaystyle \overline{5}\)；又有 \(\displaystyle \overline{181} = \overline{6}\),我们大胆地尝试如下计算：
$\(\displaystyle \overline{5} + \overline{181} = \overline{5} + \overline{6} := \overline{5+6} = \overline{4}\)$
也得出,过了 181 天是星期四.
由此受到启发,我们规定模 \(\displaystyle m\) 剩余类的加法：
$\(\displaystyle \overline{a} + \overline{b} := \overline{a+b}\)$
这样的规定是否合理呢？由于 \(\displaystyle \overline{a}, \overline{b}\) 的代表不唯一,因此需要验证：若 \(\displaystyle \overline{a}=\overline{c}, \overline{b}=\overline{d}\), 是否有 \(\displaystyle \overline{a+b} = \overline{c+d}\)？
问题
请验证这种规定模\(\displaystyle m\)剩余类的加法是合理的.
既然模 \(\displaystyle m\) 剩余类可以做加法,自然要问：它们能否做乘法呢？运用类比的方法,可以规定模 \(\displaystyle m\) 剩余类的乘法：
$\(\displaystyle \overline{a}\overline{b} = \overline{ab}\)$
类似地可以证明：这个定义是合理的,即与代表的选择无关.
这样,我们在模 \(\displaystyle m\) 剩余类组成的集合
\(\displaystyle \mathbb{Z}_m = \{\overline{0}, \overline{1}, \overline{2}, \dots, \overline{m-1}\}\)
中,规定了加法和乘法两种运算.模 \(\displaystyle m\) 剩余类是 \(\displaystyle \mathbb{Z}\) 的子集,它们也能做加法和乘法,这是数学上的一个创新点.
\(\displaystyle \mathbb{Z}_m\) 中的加法和乘法满足哪些运算法则呢？由于模 \(\displaystyle m\) 剩余类的加法和乘法分别归结为它们的代表去做相加和相乘,因此直觉判断 \(\displaystyle \mathbb{Z}_m\) 的加法和乘法满足整数的加法和乘法的运算法则,并且容易验证这一猜测是真的,即 \(\displaystyle \mathbb{Z}_m\) 的加法满足：交换律、结合律；\(\displaystyle \overline{0}\) 具有下述性质：
\[\displaystyle \overline{0} + \overline{a} = \overline{a} + \overline{0} = \overline{a}, \forall \overline{a} \in \mathbb{Z}_m\]
\(\displaystyle \overline{0}\) 称为 \(\displaystyle \mathbb{Z}_m\) 的零元；
对于 \(\displaystyle \overline{a} \in \mathbb{Z}_m\),有 \(\displaystyle \overline{-a} \in \mathbb{Z}_m\),使得
$\(\displaystyle \overline{a} + \overline{-a} = \overline{-a} + \overline{a} = \overline{0}\)$
\(\displaystyle \overline{-a}\) 称为 \(\displaystyle \overline{a}\) 的负元,记做 \(\displaystyle -\overline{a}\).
\(\displaystyle \mathbb{Z}_m\) 的乘法满足交换律、结合律,以及对加法的分配律,并且
$\(\displaystyle \overline{1}\overline{a} = \overline{a}\overline{1} = \overline{a}, \forall \overline{a} \in \mathbb{Z}_m,\)$
\(\displaystyle \overline{1}\) 称为 \(\displaystyle \mathbb{Z}_m\) 的单位元.
\(\displaystyle \mathbb{Z}_m\) 中还可以规定减法如下：
$\(\displaystyle \overline{a} - \overline{b} := \overline{a} + (-\overline{b})\)$
即减法通过加法来定义.
整数集 \(\displaystyle \mathbb{Z}\), 模 \(\displaystyle m\) 剩余类组成的集合 \(\displaystyle \mathbb{Z}_m\),它们都有加法和乘法两种运算,并且满足上述运算法则.
所有偶数组成的集合记做 \(\displaystyle 2\mathbb{Z}\),由于两个偶数的和、积仍是偶数,因此 \(\displaystyle 2\mathbb{Z}\) 也有加法和乘法两种运算.\(\displaystyle 2\mathbb{Z}\) 中不存在一个偶数具有性质：与任一偶数的乘积等于那个偶数自身.因此 \(\displaystyle 2\mathbb{Z}\) 中没有单位元.上述其他运算法则在 \(\displaystyle 2\mathbb{Z}\) 中都成立.
整数集 \(\displaystyle \mathbb{Z}\), 模 \(\displaystyle m\) 剩余类集 \(\displaystyle \mathbb{Z}_m\), 偶数集 \(\displaystyle 2\mathbb{Z}\) 有共同的特征：有加法和乘法两种运算,并且满足加法的 4 条运算法则,以及乘法的交换律、结合律,乘法对加法的分配律.我们由此抽象出现代数学的一个重要概念.不过在此之前,我们要先交代清楚：什么是集合上的运算？
\(\displaystyle \mathbb{Z}\) 中的加法运算：\(\displaystyle 3+2=5\), 实质上是把有序整数对 \(\displaystyle (3,2)\) 对应到整数 5.因此 \(\displaystyle \mathbb{Z}\) 上的加法运算是 \(\displaystyle \mathbb{Z} \times \mathbb{Z}\) 到 \(\displaystyle \mathbb{Z}\) 的一个映射,我们抓住这个主要特征,抽象出运算的概念：
定义 1.7.5（运算）
集合 \(\displaystyle S\) 上的一个二元代数运算是指 \(\displaystyle S \times S\) 到 \(\displaystyle S\) 的一个映射.
定义 1.7.6（环）
设 \(\displaystyle R\) 是一个非空集合,如果 \(\displaystyle R\) 上定义了两个代数运算,一个叫做加法,另一个叫做乘法,并且满足下列 6 条运算法则：
（1）\(\displaystyle a+b=b+a, \forall a, b \in R\) （加法交换律）；
（2）\(\displaystyle (a+b)+c=a+(b+c), \forall a, b, c \in R\) （加法结合律）；
（3）\(\displaystyle R\) 中有一个元素 \(\displaystyle 0\),且 \(\displaystyle \forall a \in R, a+0=0+a=a\) （称 \(\displaystyle 0\) 是 \(\displaystyle R\) 的零元）；
（4）任给 \(\displaystyle a \in R\),都有 \(\displaystyle b \in R\) 使得 \(\displaystyle a+b=b+a=0\),把 \(\displaystyle b\) 称为 \(\displaystyle a\) 的负元,记做 \(\displaystyle -a\)；
（5）\(\displaystyle (ab)c=a(bc), \forall a, b, c \in R\) （乘法结合律）；
（6）\(\displaystyle a(b+c)=ab+ac, (b+c)a=ba+ca, \forall a, b, c \in R\) （乘法对加法的分配律）.
那么称 \(\displaystyle R\) 是一个环 （ring）.
显然, \(\displaystyle \mathbb{Z}, \mathbb{Z}_m, 2\mathbb{Z}\) 都是环.称 \(\displaystyle \mathbb{Z}\) 是整数环, 称 \(\displaystyle \mathbb{Z}_m\) 是模 \(\displaystyle m\) 剩余类环, 称 \(\displaystyle 2\mathbb{Z}\) 是偶数环.
环 \(\displaystyle R\) 中可以定义减法运算如下：
\[\displaystyle a-b := a+(-b)\]
如果环 \(\displaystyle R\) 的乘法满足交换律,那么称 \(\displaystyle R\) 是交换环.\(\displaystyle \mathbb{Z}, \mathbb{Z}_m, 2\mathbb{Z}\) 都是交换环.
如果环 \(\displaystyle R\) 中有一个元素 \(\displaystyle \mathrm{e}\) 具有下述性质：
\[\displaystyle ea = ae = a, \quad \forall a \in R\]
那么称 \(\displaystyle \mathrm{e}\) 是 \(\displaystyle R\) 的单位元,此时 \(\displaystyle R\) 是有单位元的环.
问题
证明：在环\(\displaystyle R\)中,零元记为\(\displaystyle 0\),有\(\displaystyle 0a = a0 = 0, \forall a \in R\)
考虑模 4 剩余类环 \(\displaystyle \mathbb{Z}_4 = \{\overline{0}, \overline{1}, \overline{2}, \overline{3}\}\),显然 \(\displaystyle \overline{1}\) 是 \(\displaystyle \mathbb{Z}_4\) 的单位元.我们有
$\(\displaystyle \overline{3} \cdot \overline{3} = \overline{9} = \overline{1}\)$
由此受到启发,引出下述概念：
定义 1.7.7（可逆元）
设 \(\displaystyle R\) 是有单位元 \(\displaystyle \mathrm{e} (\neq 0)\) 的环,对于 \(\displaystyle a \in R\),如果存在 \(\displaystyle b \in R\),使得
$\(\displaystyle ab = ba = \mathrm{e}, \quad (16)\)$
那么称 \(\displaystyle a\) 是 \(\displaystyle R\) 的一个可逆元,把 \(\displaystyle b\) 叫做 \(\displaystyle a\) 的逆元,记做 \(\displaystyle a^{-1}\).
在 \(\displaystyle \mathbb{Z}_4\) 中,\(\displaystyle \overline{2}\cdot\overline{2} = \overline{4} = \overline{0}\).由此受到启发,引出下述概念.
定义 1.7.8（零因子）
设 \(\displaystyle R\) 是一个环,对于 \(\displaystyle a \in R\),如果存在 \(\displaystyle c \in R, 且 c \neq 0\),使得 \(\displaystyle ac=0\) (或 \(\displaystyle ca=0\)),那么称 \(\displaystyle a\) 是 \(\displaystyle R\) 的一个左零因子 （或右零因子）.左、右零因子统称为零因子.
可知\(\displaystyle 0\)是零因子,它被称为平凡零因子.
\(\displaystyle \mathbb{Z}_4\) 中,\(\displaystyle \overline{2}\) 是零因子,由于
$\(\displaystyle \overline{2} \cdot \overline{0} = \overline{0}, \quad \overline{2} \cdot \overline{1} = \overline{2}, \quad \overline{2} \cdot \overline{2} = \overline{0}, \quad \overline{2} \cdot \overline{3} = \overline{6} = \overline{2}\)$
因此 \(\displaystyle \overline{2}\) 不是可逆元.可猜测有下述命题：
命题
设 \(\displaystyle R\) 是有单位元 \(\displaystyle \mathrm{e} (\neq 0)\) 的环,则 \(\displaystyle R\) 的零因子不是可逆元.
命题 2 的逆否命题同样成立：设 \(\displaystyle R\) 是有单位元 \(\displaystyle \mathrm{e} (\neq 0)\) 的环,则 \(\displaystyle R\) 的可逆元不是零因子.
问题
请填写下表，求出\(\displaystyle \mathbb{Z}_2, \mathbb{Z}_3, \mathbb{Z}_4, \mathbb{Z}_5, \mathbb{Z}_6, \mathbb{Z}_7\) 以及 \(\displaystyle \mathbb{Z}\) 中的可逆元和零因子.
\begingroup
\renewcommand{\arraystretch}{1.2}
| {|>{\centering\arraybackslash}p{1.5cm}|
>{\centering\arraybackslash}p{3cm}|
>{\centering\arraybackslash}p{2.5cm}|
>{\centering\arraybackslash}p{2.5cm}|}
\multirow{2}{}{环} | \multirow{2}{}{可逆元} | \multicolumn{2}{c|}{不可逆元} | |
| --- | --- | --- | --- |
| | | 零因子 | 不是零因子 |
| \(\displaystyle \mathbb{Z}_2\) | | | |
| \(\displaystyle \mathbb{Z}_3\) | | | |
| \(\displaystyle \mathbb{Z}_4\) | | | |
| \(\displaystyle \mathbb{Z}_5\) | | | |
| \(\displaystyle \mathbb{Z}_6\) | | | |
| \(\displaystyle \mathbb{Z}_7\) | | | |
| \(\displaystyle \mathbb{Z}\) | | | |
\endgroup
观察填表的结果,我们猜想如下命题：
命题
对于任意整数 \(\displaystyle m>1\), 模 \(\displaystyle m\) 剩余类环 \(\displaystyle \mathbb{Z}_m\) 中每一个元素或者是可逆元,或者是零因子,二者必居其一,且只居其一.\footnote{将在 1.7.4 中被证明其为真.}
从上面的表格看到：\(\displaystyle \mathbb{Z}_2, \mathbb{Z}_3, \mathbb{Z}_5, \mathbb{Z}_7\) 的非零元都是可逆元.由此抽象出又一个重要的概念：
定义 1.7.11（域）
设 \(\displaystyle F\) 是一个有单位元 \(\displaystyle \mathrm{e} (\neq 0)\) 的交换环,如果 \(\displaystyle F\) 中每一个非零元都是可逆元,那么称 \(\displaystyle F\) 是一个域 （field）.
例如,\(\displaystyle \mathbb{Z}_2, \mathbb{Z}_3, \mathbb{Z}_5, \mathbb{Z}_7\) 都是域；\(\displaystyle \mathbb{Z}_4, \mathbb{Z}_6\) 不是域.
又如,有理数集 \(\displaystyle \mathbb{Q}\), 实数集 \(\displaystyle \mathbb{R}\), 复数集 \(\displaystyle \mathbb{C}\) 都是域,分别称它们为有理数域,实数域,复数域.而整数环 \(\displaystyle \mathbb{Z}\) 不是域.
如果域 \(\displaystyle F\) 中的元素都属于复数集,那么称 \(\displaystyle F\) 是数域.可以证明：最小的数域是有理数域.显然,最大的数域是复数域.
此外,根据上述观察,还可以猜测并证明下述命题：
命题
若 \(\displaystyle m\) 是合数,则 \(\displaystyle \mathbb{Z}_m\) 不是域.
从 \(\displaystyle \mathbb{Z}_2, \mathbb{Z}_3, \mathbb{Z}_5, \mathbb{Z}_7\) 都是域,我们猜测有下述命题：
命题
若 \(\displaystyle p\) 是素数,则 \(\displaystyle \mathbb{Z}_p\) 是一个域,称它为模 \(\displaystyle p\) 剩余类域.
证明该命题需要搞清楚素数的特性,于是我们考虑研究整数环的结构.
整数环的结构
整数集 \(\displaystyle \mathbb{Z}\) 中没有除法运算,但可以进行带余除法,即小学讲的同时求解商与余数的除法.
命题：带余除法
任给 \(\displaystyle a, b \in \mathbb{Z}, 且 b \neq 0\),存在唯一的一对整数 \(\displaystyle q, r\),使得
$\(\displaystyle a = qb+r, \quad 0 \leqslant r < |b|. \quad\)$
式中的 \(\displaystyle q\) 和 \(\displaystyle r\) 分别称为 \(\displaystyle a\) 被 \(\displaystyle b\) 除所得的商和余数.当 \(\displaystyle r=0\) 时,\(\displaystyle a\) 被 \(\displaystyle b\) 除得尽,由此引出整除的概念：
定义 1.7.15（整除）
对于整数 \(\displaystyle a, b\),如果存在整数 \(\displaystyle c\),使得\(\displaystyle a = cb\)，那么称 \(\displaystyle b\) 整除 \(\displaystyle a\),记做 \(\displaystyle b\mid a\)；否则,称 \(\displaystyle b\) 不能整除 \(\displaystyle a\),记做 \(\displaystyle b \nmid a\).当 \(\displaystyle b\) 整除 \(\displaystyle a\) 时,\(\displaystyle b\) 称为 \(\displaystyle a\) 的一个因数,\(\displaystyle a\) 称为 \(\displaystyle b\) 的一个倍数.
定义 1.7.16（公因数）
如果 \(\displaystyle c\mid a\) 且 \(\displaystyle c\mid b\),那么称 \(\displaystyle c\) 是 \(\displaystyle a\) 与 \(\displaystyle b\) 的一个公因数.
定义 1.7.17（最大公因数）
对于整数 \(\displaystyle a\) 与 \(\displaystyle b\) 的一个公因数 \(\displaystyle d\)， 如果\(\displaystyle a\) 与 \(\displaystyle b\) 的任一公因数都能整除 \(\displaystyle d\),那么称 \(\displaystyle d\) 是 \(\displaystyle a\) 与 \(\displaystyle b\) 的一个最大公因数（Greatest Common Divisor）,记为 \(\displaystyle d=\gcd(a,b)\)）.
当给出两个很大的正整数时,难以直接找出它们的最大公因数,因此需要探索一种统一规范的程式化方法.我们不妨从带余除法入手,探讨被除数与除数的最大公因数和除数与余数的最大公因数之间的关系.
引理
如果在 \(\displaystyle \mathbb{Z}\) 中有\(\displaystyle a = qb+r\),那么 \(\displaystyle d\) 是 \(\displaystyle a\) 与 \(\displaystyle b\) 的最大公因数当且仅当 \(\displaystyle d\) 是 \(\displaystyle b\) 与 \(\displaystyle r\) 的最大公因数.
证明
可知\(\displaystyle c\mid a \text{ 且 } c\mid b\)当且仅当\(\displaystyle c\mid b \text{ 且 } c\mid r\),设 \(\displaystyle d\) 是 \(\displaystyle a\) 与 \(\displaystyle b\) 的一个最大公因数,则\(\displaystyle d\mid b\) 且 \(\displaystyle d\mid r\).任取 \(\displaystyle b\) 与 \(\displaystyle r\) 的一个公因数 \(\displaystyle c\),则\(\displaystyle c\mid a\) 且 \(\displaystyle c\mid b\).于是 \(\displaystyle c\mid d\).因此 \(\displaystyle d\) 也是 \(\displaystyle b\) 与 \(\displaystyle r\) 的一个最大公因数.同理可证,若 \(\displaystyle d\) 是 \(\displaystyle b\) 与 \(\displaystyle r\) 的一个最大公因数,则 \(\displaystyle d\) 也是 \(\displaystyle a\) 与 \(\displaystyle b\) 的一个最大公因数.
由上述引理结合带余除法即可得出求两个整数的最大公因数的方法：
定理
任给两个整数 \(\displaystyle a, b\),都存在它们的一个最大公因数 \(\displaystyle d\),并且 \(\displaystyle d\) 可以表示成 \(\displaystyle a\) 与 \(\displaystyle b\) 的倍数和,即存在整数 \(\displaystyle u, v\),使得
\(\displaystyle ua + vb = d\)
证明
如果 \(\displaystyle b=0\),那么 \(\displaystyle a\) 是 \(\displaystyle a\) 与 \(\displaystyle 0\) 的一个最大公因数.
下设 \(\displaystyle b \neq 0\).容易看出,\(\displaystyle a\) 与 \(\displaystyle b\) 的最大公因数是 \(\displaystyle a\) 与 \(\displaystyle -b\) 的最大公因数,反之亦然.于是不妨设 \(\displaystyle b>0\).据带余除法,有整数 \(\displaystyle q_1, r_1\),使得\(\displaystyle a = q_1b+r_1, 0 \leqslant r_1 < b.\)
如果 \(\displaystyle r_1 \neq 0\),那么用 \(\displaystyle r_1\) 去除 \(\displaystyle b\),有整数 \(\displaystyle q_2, r_2\),使得\(\displaystyle b = q_2r_1+r_2, 0 \leqslant r_2 < r_1.\)
如果 \(\displaystyle r_2 \neq 0\),再用 \(\displaystyle r_2\) 去除 \(\displaystyle r_1\).如此辗转相除下去,所得余数不断减小,因此在有限步以后,必然有余数为 0.设最后三步为：
$\(\displaystyle r_{s-3} = q_{s-1}r_{s-2} + r_{s-1}, \quad 0 \leqslant r_{s-1} < r_{s-2},\)$
$\(\displaystyle r_{s-2} = q_s r_{s-1} + r_s, \quad 0 \leqslant r_s < r_{s-1},\)$
$\(\displaystyle r_{s-1} = q_{s+1}r_s + 0.\)$
由于 \(\displaystyle r_s\) 是 \(\displaystyle r_s\) 与 0 的一个最大公因数,因此从最后一个等式得出,\(\displaystyle r_s\) 是 \(\displaystyle r_{s-1}\) 与 \(\displaystyle r_s\) 的一个最大公因数.再从倒数第二个等式得出,\(\displaystyle r_s\) 是 \(\displaystyle r_{s-2}\) 与 \(\displaystyle r_{s-1}\) 的一个最大公因数.依次往上看,最后得出,\(\displaystyle r_s\) 是 \(\displaystyle a\) 与 \(\displaystyle b\) 的一个最大公因数.
从倒数第二个等式得出
$\(\displaystyle r_s = r_{s-2} - q_s r_{s-1}.\quad (*)\)$
用倒数第三个等式消去(*)式中的 \(\displaystyle r_{s-1}\).依次利用上面的等式可逐步消去 \(\displaystyle r_{s-2}, \dots, r_2, r_1\),最后得出
$\(\displaystyle r_s = ua + vb,\)$
其中 \(\displaystyle u, v\) 都是整数.
定理 2 的证明给出了求两个整数的最大公因数的统一方法,称为辗转相除法.它是一种非常重要的算法,有着广泛的应用.
定义 1.7.20（互素）
设 \(\displaystyle a, b \in \mathbb{Z}\), 如果 \(\displaystyle (a, b) = 1\), 那么称 \(\displaystyle a\) 与 \(\displaystyle b\) 互素
定义 1.7.21（贝祖定理,Bézout's theorem）
整数 \(\displaystyle a\) 与 \(\displaystyle b\) 互素当且仅当存在整数 \(\displaystyle u, v\), 使得
\(\displaystyle ua + vb = 1\)
证明
必要性可从定理2立即得出.下证明充分性。设 \(\displaystyle ua+vb=1\) 成立, 任取 \(\displaystyle a\) 与 \(\displaystyle b\) 的一个公因数 \(\displaystyle c\).
由于 \(\displaystyle c \mid a\) 且 \(\displaystyle c \mid b\), 因此 \(\displaystyle c \mid ua+vb\)，即\(\displaystyle c\mid1\).从而 \(\displaystyle c = \pm 1\), 所以 \(\displaystyle a\) 与 \(\displaystyle b\) 互素
用贝祖定理来刻画两个整数互素的特征是非常有用的.
下面我们尝试推导互素整数的一些重要性质.
性质 1：在 \(\displaystyle \mathbb{Z}\) 中, 如果 \(\displaystyle a \mid bc\), 且 \(\displaystyle (a, b) = 1\), 那么 \(\displaystyle a \mid c\).
\iffalse
证明
若 \(\displaystyle c = 0\), 则 \(\displaystyle a \mid c\).
设 $\displaystyle c \neq 0$. 由于 $\displaystyle (a, b) = 1$, 因此存在整数 $\displaystyle u, v$, 使得
\(\displaystyle ua + vb = 1.\)
两边乘以 \(\displaystyle c\) 得, \(\displaystyle uac + vbc = c\),（补充这一部分的证明）, 因此 \(\displaystyle a \mid c\).
\fi
性质 2： 在 \(\displaystyle \mathbb{Z}\) 中, 如果 \(\displaystyle a \mid c, b \mid c\), 且 \(\displaystyle (a, b) = 1\), 那么 \(\displaystyle ab \mid c\).
\iffalse
证明
由于 \(\displaystyle a \mid c\), 因此有整数 \(\displaystyle h\) 使得 \(\displaystyle c = ha\).
由于 \(\displaystyle b \mid c\), 因此 \(\displaystyle b \mid ha\)
又由于 \(\displaystyle (a, b) = 1\),由性质 1 得 \(\displaystyle b \mid h\).
从而有整数 \(\displaystyle g\) 使得, \(\displaystyle h = gb\), 由此得出\(\displaystyle c = gba\), 因此 \(\displaystyle ab \mid c\)
\fi
性质 3： 在 \(\displaystyle \mathbb{Z}\) 中, 如果 \(\displaystyle (a, c) = 1\), 且 \(\displaystyle (b, c) = 1\), 那么 \(\displaystyle (ab, c) = 1\).
\iffalse
证明
由于 \(\displaystyle (a, c) = 1\)且 \(\displaystyle (b, c) = 1\),因此有整数 \(\displaystyle u_i, v_i, i = 1, 2\), 使得
<div align="center" markdown>
\(\displaystyle u_1 a + v_1 c = 1 \text{且} u_2 b + v_2 c = 1\)
将上面两个等式相乘, 得
\(\displaystyle (u_1 u_2) ab + (u_1 a v_2 + v_1 u_2 b + v_1 v_2 c) c = 1\)
据定理 3 得 \(\displaystyle (ab, c) = 1\)
\fi
运用数学归纳法可以把性质3推广为： 在 \(\displaystyle \mathbb{Z}\) 中, 如果 \(\displaystyle (a_i, c) = 1, i = 1, 2, \cdots, s\), 那么
\(\displaystyle (a_1 a_2 \cdots a_s, c) = 1.\)运用数学归纳法并且利用性质 3 的推广, 可以把性质 2 推广为： 在 \(\displaystyle \mathbb{Z}\) 中, 如果 \(\displaystyle a_i \mid c, i = 1, 2, \cdots, s\) 且 \(\displaystyle a_1, a_2, \cdots, a_s\) 两两互素, 那么 \(\displaystyle a_1 a_2 \cdots a_s \mid c.\)
素数在整数环的结构中起基本建筑块的作用. 下面分别从几个不同的角度来刻画素数的特征:
定理
设 \(\displaystyle p\) 是大于 1 的整数, 则下列命题等价：
（1） \(\displaystyle p\) 是素数;
（2） 对任意整数 \(\displaystyle a\), 都有 \(\displaystyle p \mid a\) 或 \(\displaystyle (p, a) = 1\);
（3） 对于整数 \(\displaystyle a, b\), 从 \(\displaystyle p \mid ab\) 可以推出 \(\displaystyle p \mid a\) 或 \(\displaystyle p \mid b\);
（4） \(\displaystyle p\) 不能分解成两个比 \(\displaystyle p\) 小的正整数的乘积.
证明
采用轮回证法：
\(\displaystyle (1) \Longrightarrow (2)\)：（补充此证明）
\(\displaystyle (2) \Longrightarrow (3)\)：
设 \(\displaystyle p \mid ab\). 如果\(\displaystyle p\mid a\),则命题得证.否则,（补充这一部分的证明）, \(\displaystyle p \mid b\)
\(\displaystyle (3) \Longrightarrow (4)\)：
假如 \(\displaystyle p = p_1 p_2, 0 < p_1 < p, 0 < p_2 < p\), 由整除的反身性得, \(\displaystyle p \mid p_1 p_2\)
由 \(\displaystyle (3)\) 得： \(\displaystyle p \mid p_1\) 或 \(\displaystyle p \mid p_2\), 矛盾.
因此 \(\displaystyle p\) 不能分解成两个比 \(\displaystyle p\) 小的正整数的乘积.
\(\displaystyle (4) \Longrightarrow (1)\)：
任取 \(\displaystyle p\) 的一个正因数 \(\displaystyle a\), 则存在正整数 \(\displaystyle b\), 使得 \(\displaystyle p = ba\).
由 \(\displaystyle (4)\) 得\(\displaystyle b = p,a=1\) 或 \(\displaystyle a = p,b=1\).
因此 \(\displaystyle p\) 的正因数只有 \(\displaystyle 1\) 和 \(\displaystyle p\), 从而 \(\displaystyle p\) 是素数.
从素数的等价条件 \(\displaystyle (4)\) 得知, 大于 1 的整数 \(\displaystyle a\) 是合数当且仅当 \(\displaystyle a\) 能分解成两个比 \(\displaystyle a\) 小的正整数的乘积，如果这两个正整数中仍存在合数，则对之再次作分解，直到不能再分解为止，于是猜想对于任一大于 1 的整数 \(\displaystyle a\),它都可以被分解成有限多个素数的乘积。
定理：算术基本定理
任一大于 1 的整数 \(\displaystyle a\) 都能唯一地分解成有限多个素数的乘积. 所谓唯一性指的是, 如果 \(\displaystyle a\) 有两个分解式:
\(\displaystyle a = p_1 p_2 \cdots p_s = q_1 q_2 \cdots q_t\),
那么一定有 \(\displaystyle s = t\), 并且适当排列因数的次序后, 有
\(\displaystyle p_i = q_i(i = 1, 2, \cdots, s)\).
证明
先证明可分解性。对大于 1 的整数 \(\displaystyle n\) 用第二数学归纳法.
当 \(\displaystyle n = 2\) 时, \(\displaystyle 2\) 是素数, 命题为真.
假设对任意大于 1 且小于 \(\displaystyle n\) 的整数, 命题为真,现考虑整数 \(\displaystyle n\),
如果 \(\displaystyle n\) 是素数, 则命题为真.
如果 \(\displaystyle n\) 是合数, 那么存在正整数 \(\displaystyle n_1, n_2,1<n_1<n_2<n\), 使得 \(\displaystyle n = n_1 n_2\) ，由归纳假设， \(\displaystyle n_1\) 和 \(\displaystyle n_2\) 分别能分解成有限多个素数的乘积. 从而 \(\displaystyle n\) 能分解成有限多个素数的乘积。
再证明唯一性。假设\(\displaystyle a\) 有两个分解式 \(\displaystyle a = p_1 p_2 \cdots p_s = q_1 q_2 \cdots q_t(*)\),其中 \(\displaystyle p_i\) 和 \(\displaystyle q_j(i=1,2,\cdots,s,j=1,2,\cdots,t)\) 都是素数.对 \(\displaystyle a\) 的第一个分解式中素数的个数 \(\displaystyle s\) 作数学归纳法.
当 \(\displaystyle s = 1\) 时, \(\displaystyle a = p_1\). 于是 \(\displaystyle p_1 = q_1 q_2 \cdots q_t\). 从而 \(\displaystyle q_1 \mid p_1\). 由于 \(\displaystyle p_1\) 是素数, 因此 \(\displaystyle q_1 = p_1\), 从而 \(\displaystyle a = p_1 = q_1\). 命题为真.假设 \(\displaystyle s - 1\) 时命题为真,看 \(\displaystyle s\) 的情形.
可知 \(\displaystyle p_1 \mid q_1 q_2 \cdots q_t\). 由于 \(\displaystyle p_1\) 是素数, 因此对某个\(\displaystyle j \in \{1, 2, \cdots, t \}\) \(\displaystyle p_1 \mid q_j\), 不妨设 \(\displaystyle p_1 \mid q_1\). 由于 \(\displaystyle q_1\) 是素数, 因此 \(\displaystyle p_1 = q_1\). 于是 \(\displaystyle (*)\) 式两边可消去 \(\displaystyle p_1\), 得
$\(\displaystyle p_2 \cdots p_s = q_2 \cdots q_t\)$
由归纳假设， \(\displaystyle s - 1 = t - 1\), 且适当排列因数的次序后, 有 \(\displaystyle p_i = q_i, i = 2, \cdots, s\). 因此 \(\displaystyle s = t\), 且 \(\displaystyle p_i = q_i, i = 1, 2, \cdots, s\),唯一性得证.
算术基本定理刻画了整数环的结构:，它指出，任一大于 1 的整数 \(\displaystyle a\) 能唯一地写成
$\(\displaystyle a = p_1^{r_1} p_2^{r_2} \cdots p_m^{r_m}\)$
其中 \(\displaystyle p_1, p_2, \cdots, p_m\) 是两两不等的素数, \(\displaystyle r_i\) 是正整数, \(\displaystyle i = 1, 2, \cdots, m\).这称为 \(\displaystyle a\) 的标准分解式.
习\(\displaystyle \quad\)题
- 证明： 对一切正整数 \(\displaystyle n\), 都有 \(\displaystyle 8 \mid 9^n - 1\)
- 证明： 对一切正整数 \(\displaystyle n\), 都有 \(\displaystyle 3 \mid n(n+1)(n+2)\).
-
分别求下列各组中两个整数的正的最大公因数, 并且把它表示成这两个整数的倍数和:
（1）\(\displaystyle 126\) 与 \(\displaystyle 99\)； （2） \(\displaystyle 183\) 与 \(\displaystyle 567\)；
（3） \(\displaystyle 1023\) 与 \(\displaystyle 31\)； （4） \(\displaystyle 127\) 与 \(\displaystyle 2047\).
4. 证明： 如果 \(\displaystyle a\) 与 \(\displaystyle b\) 是不全为 \(\displaystyle 0\) 的整数, 那么
\(\displaystyle \left( \frac{a}{(a, b)}, \frac{b}{(a, b)} \right) = 1.\)
5. 证明: 在 \(\displaystyle \mathbb{Z}\) 中, 若 \(\displaystyle (a, b) = 1\), 则 \(\displaystyle (a, a+b) = 1\), 且 \(\displaystyle (ab, a+b) = 1\).
6. 写出下列整数的标准分解式:
\(\displaystyle 234, 678, 2345.\)
\(\displaystyle \mathbb{Z}_m\) 的可逆元判定, 模 \(\displaystyle p\) 剩余类域, 域的特征, 费马小定理
问题
观察问题1.29的填表结果,猜测在模 \(\displaystyle m\) 剩余类环 \(\displaystyle \mathbb{Z}_m\) 中, 当 \(\displaystyle a\) 与 \(\displaystyle m\) 有什么关系时, \(\displaystyle \overline{a}\) 是 \(\displaystyle \mathbb{Z}_m\) 的可逆元？ 当 \(\displaystyle a\) 与 \(\displaystyle m\) 有什么关系时, \(\displaystyle \overline{a}\) 是 \(\displaystyle \mathbb{Z}_m\) 的零因子？
从上述问题受到启发,我们可以提出并证明下述定理：
定理
在模 \(\displaystyle m\) 剩余类环 \(\displaystyle \mathbb{Z}_m\) 中, \(\displaystyle \overline{a}\) 是可逆元当且仅当 \(\displaystyle a\) 与 \(\displaystyle m\) 互素.
证明
先证充分性。设 \(\displaystyle a\) 与 \(\displaystyle m\) 互素, 则存在整数 \(\displaystyle u, v\)使得\(\displaystyle ua + vm = 1\)，即\(\displaystyle \overline{u}\cdot \overline{a}+\overline{v}\cdot \overline{m} = \overline{1}\), 而\(\displaystyle \overline{v}\cdot \overline{m} = \overline{0}\), 从而 \(\displaystyle \overline{u}\cdot \overline{a} = \overline{1}\), 于是 \(\displaystyle \overline{u}\) 是 \(\displaystyle \overline{a}\) 的逆元.\(\displaystyle \overline{a}\) 是可逆元。
再证必要性。设 \(\displaystyle \overline{a}\) 是 \(\displaystyle \mathbb{Z}_m\) 的可逆元, 其中 \(\displaystyle 0 < a < m\)。用反证法，假设 \(\displaystyle a\) 与 \(\displaystyle m\) 不互素, 设它们的一个公因数为\(\displaystyle d>1\)，则存在整数\(\displaystyle n_1,n_2\)使得\(\displaystyle n_1d=a,n_2d=m\)，于是\(\displaystyle n_1n_2d=n_2a=n_1m\)，即\(\displaystyle \overline{n_2}\cdots \overline{n_1} =\overline{n_1}\cdot \overline{m}= \overline{0}\)，所以\(\displaystyle \overline{a}\) 是零因子，这与 \(\displaystyle \overline{a}\) 是可逆元矛盾. 因此 \(\displaystyle a\) 与 \(\displaystyle m\) 互素.
从定理 1 的充分性的证明看到： 若 \(\displaystyle a\) 与 \(\displaystyle m\) 互素, 则 \(\displaystyle \overline{a}\) 是可逆元. 从定理 1 的必要性的证明看到： 设 \(\displaystyle 0 < a < m\), 若 \(\displaystyle a\) 与 \(\displaystyle m\) 不互素, 则 \(\displaystyle \overline{a}\) 是零因子, 于是立即得到：
定理
\(\displaystyle \mathbb{Z}_m\) 的每一个元素或者是可逆元, 或者是零因子.
设 \(\displaystyle p\) 是素数, 则对于 \(\displaystyle 0 < k < p\), 有 \(\displaystyle p \nmid k\), 从而 \(\displaystyle k\) 与 \(\displaystyle p\) 互素. 于是在 \(\displaystyle \mathbb{Z}_p\) 中, 每个非零元 \(\displaystyle \overline{k}\) 都可逆, 因此我们证明了下述定理
定理
若 \(\displaystyle p\) 是素数, 则 \(\displaystyle \mathbb{Z}_p\) 是域
定理 1 充分性的证明给出了当 \(\displaystyle a\) 与 \(\displaystyle m\) 互素时, 求 \(\displaystyle \overline{a}\) 的逆元的方法：对 \(\displaystyle a\) 和 \(\displaystyle m\) 用辗转相除法求出它们的正最大公因数 1, 然后把 1 表示成 \(\displaystyle a\) 与 \(\displaystyle m\) 的倍数和, 据此得到 \(\displaystyle \overline{a}\) 的逆元.
在环 \(\displaystyle R\) 中有加法运算, 据此可定义元素 \(\displaystyle a\) 的正整数倍.
定义 1.7.27
对于任一正整数 \(\displaystyle n\), 规定 \(\displaystyle a\) 的 \(\displaystyle n\) 倍为：\(\displaystyle na := \underbrace{a + a + \cdots + a}_{n \text{ 个}}\)
设 \(\displaystyle a \in R, n, m \in \mathbb{N}^*\),由上述定义可推导出：
$\(\displaystyle (n + m)a = na + ma, (nm)a = n(ma)\)$
$\(\displaystyle n(a + b) = na + nb,n(ab) = (na)b = a(nb)\)$
对于自然数 \(\displaystyle 0\), 可以定义 \(\displaystyle a\) 的 \(\displaystyle 0\) 倍为： \(\displaystyle 0a = 0\), 其中等号右边的 \(\displaystyle 0\) 是环 \(\displaystyle R\) 中的零元.
下面来讨论模 \(\displaystyle p\) 剩余类域 \(\displaystyle \mathbb{Z}_p\) 与数域的不同点.
在 \(\displaystyle \mathbb{Z}_2\) 中, \(\displaystyle 2 \overline{1} = \overline{1} + \overline{1} = \overline{2} = \overline{0}\)
在 \(\displaystyle \mathbb{Z}_3\) 中, \(\displaystyle 3 \overline{1} = \overline{1} + \overline{1} + \overline{1} = \overline{3} = \overline{0}; \ 2 \overline{1} = \overline{2} \neq \overline{0}\)
设 \(\displaystyle p\) 是素数, 则在 \(\displaystyle \mathbb{Z}_p\) 中, 有
\(\displaystyle p\overline{1} = \overline{p} = \overline{0}\),当\(\displaystyle 0<l<p\)时,\(\displaystyle l\overline{1} = \overline{l} \neq \overline{0}\)
在数域 \(\displaystyle K\) 中, 对于任意正整数 \(\displaystyle n\), 都有 \(\displaystyle n1 = n \neq 0\), 只有 \(\displaystyle 1\) 的 \(\displaystyle 0\) 倍等于 \(\displaystyle 0\).
我们可以探索：任一域 \(\displaystyle F\), 它的单位元 \(\displaystyle \mathrm{e}\) 的正整数倍是否等于零元？ 有什么规律？
情形 1： 对任意正整数 \(\displaystyle n\), 都有 \(\displaystyle ne \neq 0\).
情形 2： 存在正整数 \(\displaystyle n\), 使得 \(\displaystyle ne = 0\), 并设 \(\displaystyle n\) 是使 \(\displaystyle ne = 0\) 成立的最小正整数.
假如 \(\displaystyle n\) 不是素数, 则
\(\displaystyle n = n_1 n_2, 1 < n_1 < n,1 < n_2 < n\),于是有
$\(\displaystyle (n_1 \mathrm{e})(n_2 \mathrm{e}) &= n_1 [\mathrm{e}(n_2 \mathrm{e})] = n_1 [n_2 (ee)] = n_1 (n_2 \mathrm{e}) = (n_1 n_2)\mathrm{e}
&= ne = 0.\)$
而 \(\displaystyle n_1 \mathrm{e} \neq 0\) 且 \(\displaystyle n_2 \mathrm{e} \neq 0\),于是 \(\displaystyle n_1 \mathrm{e}\) 是零因子, 从而 \(\displaystyle n_1 \mathrm{e}\) 不是可逆元, 这与 \(\displaystyle F\) 是域矛盾, 因此 \(\displaystyle n\) 是素数.
于是证明了下述定理：
定理
设域 \(\displaystyle F\) 的单位元为 \(\displaystyle \mathrm{e}\), 则或者对任意正整数 \(\displaystyle n\), 都有 \(\displaystyle ne \neq 0\)； 或者存在一个素数 \(\displaystyle p\), 使得 \(\displaystyle pe = 0\), 而对于 \(\displaystyle 0 < l < p\), 有 \(\displaystyle le \neq 0\)
从该定理受到启发, 引出下述重要概念
定义 1.7.29（域的特征）
设域 \(\displaystyle F\) 的单位元为 \(\displaystyle \mathrm{e}\), 如果对任意正整数 \(\displaystyle n\), 都有 \(\displaystyle ne \neq 0\), 那么称域 \(\displaystyle F\) 的特征为 \(\displaystyle 0\)； 如果存在一个素数 \(\displaystyle p\), 使得 \(\displaystyle pe = 0\), 而对于 \(\displaystyle 0 < l < p\), 有 \(\displaystyle le \neq 0\), 那么称域 \(\displaystyle F\) 的特征为 \(\displaystyle p\), 域 \(\displaystyle F\) 的特征记做 \(\displaystyle \text{char} F\).
据定理4, 任一域 \(\displaystyle F\) 的特征或者为 \(\displaystyle 0\), 或者为一个素数,例如模素数 \(\displaystyle p\) 剩余类域 \(\displaystyle \mathbb{Z}_p\) 的特征为 \(\displaystyle p\),任一数域的特征为 \(\displaystyle 0\), 这就是 \(\displaystyle \mathbb{Z}_p\) 与数域的本质区别.
在特征为素数 \(\displaystyle p\) 的域 \(\displaystyle F\) 中,单位元 \(\displaystyle \mathrm{e}\) 的 \(\displaystyle p\) 倍等于零元,我们自然要问: 任一元素 \(\displaystyle a\) 的 \(\displaystyle p\) 倍是否也等于零元？
命题
设域 \(\displaystyle F\) 的特征为素数 \(\displaystyle p\), 则对 \(\displaystyle F\) 中任一元素 \(\displaystyle a\), 都有 \(\displaystyle pa = 0\).
证明
设 \(\displaystyle F\) 的单位元为 \(\displaystyle \mathrm{e}\), 则
\(\displaystyle pa = p(ea) = (pe)a = 0a = 0\)
在特征为素数 \(\displaystyle p\) 的域 \(\displaystyle F\) 中, 由于任一元素的 \(\displaystyle p\) 倍都等于 \(\displaystyle 0\), 因此可以简化计算.
问题
证明：在 \(\displaystyle \mathbb{Z}_3\) 中,元素\(\displaystyle \overline{a}, \overline{b}\) 满足
$\(\displaystyle (\overline{a} + \overline{b})^3 = \overline{a}^3 + \overline{b}^3\)$
由此受到启发,提出下述命题：
命题
设域 \(\displaystyle F\) 的特征为素数 \(\displaystyle p\), 则对于任意 \(\displaystyle a, b \in F\), 有
$\(\displaystyle (a+b)^p = a^p + b^p\)$
证明
由于域 \(\displaystyle F\) 具有与实数域同样的运算规则,因此在域 \(\displaystyle F\) 中也有二项式定理：
$\(\displaystyle (a+b)^p = a^p + \mathrm{C}_p^1 a^{p-1}b + \cdots + \mathrm{C}_p^k a^{p-k}b^k + \cdots + \mathrm{C}_p^{p-1} ab^{p-1} + b^p\)$
其中\(\displaystyle \mathrm{C}_p^k = \frac{p(p-1)\cdots(p-k+1)}{k!},1 \leqslant k < p\).当 \(\displaystyle 1 \leqslant k < p\) 时,有\(\displaystyle (k!, p) = 1\),
由于 \(\displaystyle \mathrm{C}_p^k\in\mathbb{Z}\),则\(\displaystyle k! \mid p(p-1)\cdots(p-k+1)\),因此
$\(\displaystyle k! \mid (p-1)\cdots(p-k+1), 1 \leqslant k < p\)$
可得
$\(\displaystyle p \mid C_p^k \quad 1 \leqslant k < p\)$
即
$\(\displaystyle (a+b)^p = a^p + b^p\)$
\paragraph{例 2} \(\displaystyle 2^{97}\) 模 \(\displaystyle 97\) 同余于几？ \(\displaystyle 90^{97}\) 模 \(\displaystyle 97\) 同余于几？
解： \(\displaystyle 97\) 是素数,于是域 \(\displaystyle \mathbb{Z}_{97}\) 的特征为 \(\displaystyle 97\). 在 \(\displaystyle \mathbb{Z}_{97}\) 中有
\[\displaystyle \overline{2^{97}} = \overline{2}^{97} = (\overline{1} + \overline{1})^{97} = \overline{1}^{97} + \overline{1}^{97} = \overline{1} + \overline{1} = \overline{2}\]
\[\displaystyle \overline{90^{97}} = \overline{90}^{97} = (\underbrace{\overline{1} + \overline{1} + \cdots + \overline{1}}_{90 \text{ 个}})^{97} = \underbrace{\overline{1}^{97} + \overline{1}^{97} + \cdots + \overline{1}^{97}}_{90 \text{ 个}} = \overline{90}\]
可得
$\(\displaystyle 2^{97} \equiv 2 \pmod{97}, 90^{97} \equiv 90 \pmod{97}\)$
从例 2 受到启发,可以猜测并证明下述定理：
定理：费马小定理（Fermat's Little Theorem）
设 \(\displaystyle p\) 是素数,则对于任意整数 \(\displaystyle a\),都有
$\(\displaystyle a^p \equiv a \pmod{p}\)$
证明
若 \(\displaystyle p \mid a\),则 \(\displaystyle a \equiv 0 \pmod{p}\) 且 \(\displaystyle a^p \equiv 0 \pmod{p}\),从而 \(\displaystyle a^p \equiv a \pmod{p}\)
下面设 \(\displaystyle p \nmid a\), 作带余除法，\(\displaystyle a = hp + r, 0 < r < p\)，在 \(\displaystyle \mathbb{Z}_p\) 中,有
\(\displaystyle \overline{a} = \overline{hp + r} = \overline{r}\)，
由于 \(\displaystyle \mathbb{Z}_p\) 的特征为 \(\displaystyle p\),因此
$\(\displaystyle \overline{a}^p = \overline{r}^p &= (\underbrace{\overline{1} + \overline{1} + \cdots + \overline{1}}_{r 个})^p = \underbrace{\overline{1}^p + \overline{1}^p + \cdots + \overline{1}^p}_{r 个}
&= \underbrace{\overline{1} + \overline{1} + \cdots + \overline{1}}_{r 个} = \overline{r} = \overline{a}\)$
即\(\displaystyle a^p \equiv a \pmod{p}\)
- 分别写出 \(\displaystyle \mathbb{Z}_{18}, \mathbb{Z}_{36}\) 的所有可逆元和所有零因子.
- 在 \(\displaystyle \mathbb{Z}_{86}\) 中,\(\displaystyle \overline{3}, \overline{35}\) 是不是可逆元？如果是,分别求它们的逆元.
- 在 \(\displaystyle \mathbb{Z}_{89}\) 中,求 \(\displaystyle \overline{2}, \overline{86}\) 的逆元；在 \(\displaystyle \mathbb{Z}_{113}\) 中,求 \(\displaystyle \overline{36}, \overline{48}\) 的逆元.
- 设 \(\displaystyle F\) 是特征为 \(\displaystyle 2\) 的域,任给 \(\displaystyle a, b \in F\),计算：
\(\displaystyle (a+b)^2, (a+b)^4, (a+b)^8\),由此你能猜测 \(\displaystyle (a+b)^{2^n}\) 等于多少吗？你能证明这个猜测是真的吗？
- 求\(\displaystyle 2010^{79}\text{ mod } 79, 2010^{127}\text{ mod } 127\).
-
设域 \(\displaystyle F\) 的特征为素数 \(\displaystyle p\),证明：对任意 \(\displaystyle a_1, a_2, \cdots, a_s \in F\),有
$\(\displaystyle (a_1 + a_2 + \cdots + a_s)^p = a_1^p + a_2^p + \cdots + a_s^p\)$
（提示：使用数学归纳法）
中国剩余定理
设这个连有 \(\displaystyle x\) 名战士,按照上述已知条件,得
\(\displaystyle \begin{cases} x \equiv 2 \pmod{3}, \\ x \equiv 4 \pmod{5}, \\ x \equiv 2 \pmod{7}. \end{cases} (1)\)
这样的方程组叫做一次同余方程组. 如何解这种一次同余方程组呢？它有多
少解呢？
一般地,设 \(\displaystyle m_1, m_2, \cdots, m_s\) 是两两互素的大于 \(\displaystyle 1\) 的整数,\(\displaystyle b_1, b_2, \cdots, b_s\) 是任意给定的整数,考虑一次同余方程组：
\(\displaystyle \begin{cases} x \equiv b_1 \pmod{m_1}, \\ x \equiv b_2 \pmod{m_2}, \\ \dots \dots \dots \dots \dots \\ x \equiv b_s \pmod{m_s}. \end{cases} \hfill (2)\)
我们来探索如何求同余方程组 \(\displaystyle (2)\) 的解？它有多少解？
由于 \(\displaystyle m_1, m_2, \cdots, m_s\) 两两互素,因此对于 \(\displaystyle i \in \{1, 2, \cdots, s\}\),有
$\(\displaystyle \left( m_i, \prod_{j \neq i} m_j \right) = 1, \hfill\)$
从而存在 \(\displaystyle u_i, v_i \in \mathbb{Z}\),使得
$\(\displaystyle u_i m_i + v_i \prod_{j \neq i} m_j = 1.\)$
由上式得到
\[\displaystyle v_i \prod_{j \neq i} m_j = 1 - u_i m_i\]
从而有
\[\displaystyle \begin{cases} v_i \prod_{j \neq i} m_j \equiv 1 \pmod{m_i}, \\ v_i \prod_{j \neq i} m_j \equiv 0 \pmod{m_k}, \quad k \neq i. \end{cases} \hfill\]
由于同余方程组 \(\displaystyle (2)\) 的解应当满足模 \(\displaystyle m_i\) 同余于 \(\displaystyle b_i (i = 1, 2, \cdots, s)\),因此,令
\[\displaystyle c = b_1 v_1 \prod_{j \neq 1} m_j + \cdots + b_i v_i \prod_{j \neq i} m_j + \cdots + b_s v_s \prod_{j \neq s} m_j\]
则
\[\displaystyle c \equiv b_1 \cdot 0 + \cdots + b_i \cdot 1 + \cdots + b_s \cdot 0 \equiv b_i \pmod{m_i}\]
其中 \(\displaystyle i = 1, 2, \cdots, s\). 因此,由 \(\displaystyle (7)\) 式定义的 \(\displaystyle c\) 是同余方程组 \(\displaystyle (2)\) 的一个解.
若 \(\displaystyle d\) 也是同余方程组 \(\displaystyle (2)\) 的一个解,则
\[\displaystyle c \equiv d \pmod{m_i}, \quad i = 1, 2, \cdots, s$$
从而
$$\displaystyle m_i \mid c - d, \quad i = 1, 2, \cdots, s$$
由于 $\displaystyle m_1, m_2, \cdots, m_s$ 两两互素,因此
$$\displaystyle m_1 m_2 \cdots m_s \mid c - d, \hfill$$
由此得出
$$\displaystyle c \equiv d \pmod{m_1 m_2 \cdots m_s}\]
上述的探索过程发现并且证明了下述定理：
定理：中国剩余定理
设 \(\displaystyle m_1, m_2, \cdots, m_s\) 是两两互素的大于 \(\displaystyle 1\) 的整数,则对于任意给定的整数 \(\displaystyle b_1, b_2, \cdots, b_s\),一次同余方程组
$\(\displaystyle \begin{cases} x \equiv b_1 \pmod{m_1}, \\ x \equiv b_2 \pmod{m_2}, \\ \dots \dots \dots \dots \dots \\ x \equiv b_s \pmod{m_s}. \end{cases}\)$
在 \(\displaystyle \mathbb{Z}\) 中有解,它的全部解是
$\(\displaystyle c + k m_1 m_2 \cdots m_s, \quad k \in \mathbb{Z}\)$
其中
$\(\displaystyle c = b_1 v_1 \prod_{j \neq 1} m_j + b_2 v_2 \prod_{j \neq 2} m_j + \cdots + b_s v_s \prod_{j \neq s} m_j\)$
\(\displaystyle v_i\) 满足 \(\displaystyle u_i m_i + v_i \prod_{j \neq i} m_j = 1, i = 1, 2, \cdots, s.\)
从定理 1 看出,为了求一次同余方程组 \(\displaystyle (12)\) 的全部解,需要先求出 \(\displaystyle v_i (i = 1, 2, \cdots, s)\),而这只要对 \(\displaystyle m_i\) 和 \(\displaystyle \prod_{j \neq i} m_j\) 作辗转相除法,并且把它们的最大公因数 \(\displaystyle 1\) 表示成它们的倍数和,此时 \(\displaystyle \prod_{j \neq i} m_j\) 的倍数就是 \(\displaystyle v_i\).
我国南宋数学家秦九韶在他的著作《数书九章》卷一“大衍总数术”中,系统地叙述了求解一次同余方程组的一般方法,其关键部分就是求 \(\displaystyle (14)\) 式中的 \(\displaystyle v_i (i = 1, 2, \cdots, s)\). 秦九韶把他自己发现的求 \(\displaystyle v_i\) 的方法称为“大衍求一术”,实际上就是做辗转相除法.
秦九韶的算法是正确的,但他本人没有给出证明.而欧拉和高斯分别在 \(\displaystyle 1743\) 年、\(\displaystyle 1801\) 年对一次同余方程组进行了详细研究,重新独立地获得与秦九韶“大衍求一术”相同的定理,并对模数两两互素的情形作出了严格证明. \(\displaystyle 1876\) 年德国人马蒂生首先指出秦九韶的方法与高斯算法是一致的,因此,关于一次同余方程组求解的剩余定理通常被称为“中国剩余定理”.
- 设 \(\displaystyle m_1\) 和 \(\displaystyle m_2\) 是互素的大于 \(\displaystyle 1\) 的整数,\(\displaystyle b\) 是任意给定的一个整数. 证明：整数 \(\displaystyle a\) 满足
\(\displaystyle \begin{cases} a \equiv b \pmod{m_1}, \\ a \equiv b \pmod{m_2} \end{cases}\)
的充分必要条件是 \(\displaystyle a \equiv b \pmod{m_1 m_2}\).
\(\displaystyle \mathbb{Z}_m\) 的可逆元的个数,欧拉函数
我们之前证明了：在模 \(\displaystyle m\) 剩余类环 \(\displaystyle \mathbb{Z}_m\) 中,\(\displaystyle \overline{a}\) 是可逆元当且仅当 \(\displaystyle a\) 与 \(\displaystyle m\) 互素.把 \(\displaystyle \mathbb{Z}_m\) 中所有可逆元组成的集合记做 \(\displaystyle \mathbb{Z}_m^*\), 我们首先要问：\(\displaystyle \mathbb{Z}_m^*\) 有多少个元素？
定义 1.7.34（欧拉函数）
设 \(\displaystyle m\) 是大于 \(\displaystyle 1\) 的整数,把 \(\displaystyle \mathbb{Z}_m\) 中可逆元的个数记做 \(\displaystyle \varphi(m)\),称 \(\displaystyle \varphi(m)\) 为欧拉函数.
可知, \(\displaystyle \varphi(m)\) 等于集合 \(\displaystyle \Omega_m = \{1, 2, 3, \cdots, m\}\) 中与 \(\displaystyle m\) 互素的整数的个数.
| {|c|l|c|}
| \(\displaystyle m\) |
\(\displaystyle 1\sim m\) 中与 \(\displaystyle m\) 互素的整数 |
\(\displaystyle \varphi(m)\) |
| \(\displaystyle 2\) |
|
|
| \(\displaystyle 3\) |
|
|
| \(\displaystyle 4\) |
|
|
| \(\displaystyle 5\) |
|
|
| \(\displaystyle 6\) |
|
|
| \(\displaystyle 7\) |
|
|
| \(\displaystyle 8\) |
|
|
| \(\displaystyle 9\) |
|
|
| \(\displaystyle 12\) |
|
|
| \(\displaystyle 15\) |
|
|
| \(\displaystyle 24\) |
|
|
观察填写后的表,当 \(\displaystyle m\) 为素数\(\displaystyle 2, 3, 5, 7\) 时,\(\displaystyle \varphi(m)\) 的值有何规律？
由此受到启发,猜测且容易证明下述命题：
\paragraph{命题 2} 若 \(\displaystyle p\) 是素数,则 \(\displaystyle \varphi(p) = p - 1\).
问题
观察上表中\(\displaystyle \varphi(4)=\varphi(2^2), \varphi(8)=\varphi(2^3), \varphi(9)=\varphi(3^2)\)的值,你能作出什么猜测？
定理
设 \(\displaystyle p\) 是素数,对任意正整数 \(\displaystyle r\),有
$\(\displaystyle \varphi(p^r) = p^{r-1}(p - 1)\)$
问题
完成该定理的证明.（提示：考虑\(\displaystyle 1,2,\cdots,p^r\)中与\(\displaystyle p^r\)不互素的数的个数。）
问题
回答下述问题：
（1）\(\displaystyle \varphi(6)\)与\(\displaystyle \varphi(2)\varphi(3)\)相等吗？
（2）\(\displaystyle \varphi(15)\)与\(\displaystyle \varphi(3)\varphi(5)\)相等吗？
（3）\(\displaystyle \varphi(12)\)与\(\displaystyle \varphi(2)\varphi(6)\)相等吗？\(\displaystyle \varphi(3)\varphi(4)\)呢？
（4）\(\displaystyle \varphi(24)\)与\(\displaystyle \varphi(4)\varphi(6)\)相等吗？\(\displaystyle \varphi(3)\varphi(8)\)呢？
（5）设\(\displaystyle m=m_1m_2,m_1,m_2\)是大于1的整数,如果\(\displaystyle \varphi(m)=\varphi(m_1)\varphi(m_2)\),猜测\(\displaystyle m_1,m_2\)应该满足什么关系？
猜测有下述结论：
设 \(\displaystyle m = m_1 m_2\),且 \(\displaystyle m_1\) 与 \(\displaystyle m_2\) 是互素的大于 \(\displaystyle 1\) 的整数,则
\(\displaystyle \varphi(m) = \varphi(m_1) \varphi(m_2)\)
这个猜测是真是假？我们来探索.
\(\displaystyle \varphi(m_1)\) 是 \(\displaystyle \mathbb{Z}_{m_1}\) 中可逆元的个数,\(\displaystyle \varphi(m_2)\) 是 \(\displaystyle \mathbb{Z}_{m_2}\) 中可逆元的个数.\(\displaystyle \varphi(m_1) \varphi(m_2)\) 是什么呢？
一个创新的想法是考虑集合 \(\displaystyle \mathbb{Z}_{m_1}\) 与 \(\displaystyle \mathbb{Z}_{m_2}\) 的笛卡儿积：
\[\displaystyle \mathbb{Z}_{m_1} \times \mathbb{Z}_{m_2} = \{ (\widetilde{a}_1, \widetilde{\widetilde{a}}_2) \mid \widetilde{a}_1 \in \mathbb{Z}_{m_1}, \widetilde{\widetilde{a}}_2 \in \mathbb{Z}_{m_2} \}\]
并规定它的加法和乘法运算如下：
\[\displaystyle (\widetilde{a}_1, \widetilde{\widetilde{a}}_2) + (\widetilde{b}_1, \widetilde{\widetilde{b}}_2) := (\widetilde{a}_1 + \widetilde{b}_1, \widetilde{\widetilde{a}}_2 + \widetilde{\widetilde{b}}_2)\]
\[\displaystyle (\widetilde{a}_1, \widetilde{\widetilde{a}}_2)(\widetilde{b}_1, \widetilde{\widetilde{b}}_2) := (\widetilde{a}_1 \widetilde{b}_1, \widetilde{\widetilde{a}}_2 \widetilde{\widetilde{b}}_2)\]
容易验证 \(\displaystyle \mathbb{Z}_{m_1} \times \mathbb{Z}_{m_2}\) 称为一个有单位元\(\displaystyle (\widetilde{1},\widetilde{\widetilde{1}})\)的交换环,把这个环叫做环 \(\displaystyle \mathbb{Z}_{m_1}\) 与 \(\displaystyle \mathbb{Z}_{m_2}\) 的直和,记做 \(\displaystyle \mathbb{Z}_{m_1} \oplus \mathbb{Z}_{m_2}\).
问题
解答下述问题：
（1）证明：\(\displaystyle (\widetilde{a}_1, \widetilde{\widetilde{a}}_2)\) 是 \(\displaystyle \mathbb{Z}_{m_1} \oplus \mathbb{Z}_{m_2}\) 的可逆元当且仅当 \(\displaystyle \widetilde{a}_1, \widetilde{\widetilde{a}}_2\) 分别是 \(\displaystyle \mathbb{Z}_{m_1}, \mathbb{Z}_{m_2}\) 的可逆元.
（2）据第（1）问,证明：\(\displaystyle \mathbb{Z}_{m_1} \oplus \mathbb{Z}_{m_2}\) 的可逆元的个数等于 \(\displaystyle \varphi(m_1) \varphi(m_2)\)
上述结论给出了 \(\displaystyle \varphi(m_1) \varphi(m_2)\) 一个结构性解释,这是一个创新点.
既然待证等式的右端是 \(\displaystyle \mathbb{Z}_{m_1} \oplus \mathbb{Z}_{m_2}\) 的可逆元的个数,左端是 \(\displaystyle \mathbb{Z}_m\) 的可逆元的个数,我们自然要研究环 \(\displaystyle \mathbb{Z}_{m_1} \oplus \mathbb{Z}_{m_2}\) 与环 \(\displaystyle \mathbb{Z}_m\) 的关系.
首先建立 \(\displaystyle \mathbb{Z}_m\) 的元素与 \(\displaystyle \mathbb{Z}_{m_1} \oplus \mathbb{Z}_{m_2}\) 的元素之间的对应关系.
容易想到,令
\(\displaystyle \sigma: \mathbb{Z}_m \longrightarrow \mathbb{Z}_{m_1} \oplus \mathbb{Z}_{m_2}\)
$\displaystyle \overline{x} \longmapsto (\widetilde{x}, \widetilde{\widetilde{x}})$
问题
解答下述问题：
（1）验证\(\displaystyle \sigma\)是\(\displaystyle \mathbb{Z}_m\) 到 \(\displaystyle \mathbb{Z}_{m_1} \oplus \mathbb{Z}_{m_2}\) 的一个映射.
（2）证明：\(\displaystyle \sigma\)是双射；
（3）证明：\(\displaystyle \forall x,y\in\mathbb{Z}_m\),有
\(\displaystyle \sigma(\overline{x}+\overline{y})=\sigma(\overline{x})+\sigma(\overline{y}),\sigma(\overline{x} \overline{y})=\sigma(\overline{x})\sigma(\overline{y})\)
这称为\(\displaystyle \sigma\)保持加法和乘法运算.
\paragraph{定义 2 （环同构）}如果环 \(\displaystyle R\) 到环 \(\displaystyle R'\) 有一个双射 \(\displaystyle \sigma\),且 \(\displaystyle \sigma\) 保持加法和乘法运算,那么称 \(\displaystyle \sigma\) 是环 \(\displaystyle R\) 到 \(\displaystyle R'\) 的一个同构映射,此时称环 \(\displaystyle R\) 与环 \(\displaystyle R'\) 是同构的,记做 \(\displaystyle R \cong R'\).
从上面的讨论得出：
\paragraph{定理 3} 设 \(\displaystyle m = m_1 m_2\),且 \(\displaystyle m_1\) 与 \(\displaystyle m_2\) 是互素的大于 \(\displaystyle 1\) 的整数,则 \(\displaystyle \sigma: \overline{x} \longmapsto (\overline{x}, \tilde{\tilde{x}})\) 是环 \(\displaystyle \mathbb{Z}_m\) 到 \(\displaystyle \mathbb{Z}_{m_1} \oplus \mathbb{Z}_{m_2}\) 的一个同构映射,从而环 \(\displaystyle \mathbb{Z}_m\) 与 \(\displaystyle \mathbb{Z}_{m_1} \oplus \mathbb{Z}_{m_2}\) 同构.
利用环 \(\displaystyle \mathbb{Z}_m\) 到 \(\displaystyle \mathbb{Z}_{m_1} \oplus \mathbb{Z}_{m_2}\) 的同构映射 \(\displaystyle \sigma\) 可以探讨 \(\displaystyle \mathbb{Z}_m\) 的可逆元与 \(\displaystyle \mathbb{Z}_{m_1} \oplus \mathbb{Z}_{m_2}\) 的可逆元之间的关系.
\[\displaystyle & \overline{x} 是 \mathbb{Z}_m 的可逆元
\iff & 存在 \overline{b} \in \mathbb{Z}_m, 使得 \overline{x} \overline{b} = \overline{1}
\iff & 存在 \overline{b} \in \mathbb{Z}_m, 使得 \sigma(\overline{1}) = \sigma(\overline{x} \overline{b}) = \sigma(\overline{x})\sigma(\overline{b})
\iff & \sigma(\overline{x}) 是 \mathbb{Z}_{m_1} \oplus \mathbb{Z}_{m_2} 的可逆元.\]
上述表明：\(\displaystyle \sigma\) 诱导了 \(\displaystyle \mathbb{Z}_m^*\) 到 \(\displaystyle (\mathbb{Z}_{m_1} \oplus \mathbb{Z}_{m_2})^*\) 的一个双射.于是 \(\displaystyle |\mathbb{Z}_m^*| = |(\mathbb{Z}_{m_1} \oplus \mathbb{Z}_{m_2})^*|\).因此,\(\displaystyle \varphi(m) = \varphi(m_1) \varphi(m_2)\).这样我们证明了前面作出的猜测是真的,即
\paragraph{定理 4} 设 \(\displaystyle m = m_1 m_2\),且 \(\displaystyle m_1\) 与 \(\displaystyle m_2\) 是互素的大于 \(\displaystyle 1\) 的整数,则
\(\displaystyle \varphi(m) = \varphi(m_1) \varphi(m_2)\).
我们证明定理 4 的方法是运用现代数学研究结构和态射（即保持运算的映射）的观点,第一步证明 \(\displaystyle \varphi(m_1) \varphi(m_2)\) 是环 \(\displaystyle \mathbb{Z}_{m_1} \oplus \mathbb{Z}_{m_2}\) 的可逆元的个数；第二步建立环 \(\displaystyle \mathbb{Z}_m\) 到 \(\displaystyle \mathbb{Z}_{m_1} \oplus \mathbb{Z}_{m_2}\) 的一个映射 \(\displaystyle \sigma: \overline{x} \longmapsto (\overline{x}, \tilde{\tilde{x}})\),证明 \(\displaystyle \sigma\) 是满射,从而 \(\displaystyle \sigma\) 是单射,于是 \(\displaystyle \sigma\) 是双射；且证明 \(\displaystyle \sigma\) 保持加法和乘法运算,因此 \(\displaystyle \sigma\) 是环 \(\displaystyle \mathbb{Z}_m\) 到 \(\displaystyle \mathbb{Z}_{m_1} \oplus \mathbb{Z}_{m_2}\) 的一个同构映射.由此得出,\(\displaystyle \overline{a}\) 是 \(\displaystyle \mathbb{Z}_m\) 的可逆元当且仅当 \(\displaystyle \sigma(\overline{a})\) 是 \(\displaystyle \mathbb{Z}_{m_1} \oplus \mathbb{Z}_{m_2}\) 的可逆元.
问题
设\(\displaystyle m = p_1^{r_1} p_2^{r_2} \dots p_s^{r_s}\),其中 \(\displaystyle p_1, p_2, \dots, p_s\) 是两两不等的素数,证明：
$\(\displaystyle \varphi(m) = p_1^{r_1-1}(p_1 - 1) p_2^{r_2-1}(p_2 - 1) \dots p_s^{r_s-1}(p_s - 1)\)$
并求 \(\displaystyle \varphi(360)\) 的值.
- 写出 \(\displaystyle \mathbb{Z}_4 \oplus \mathbb{Z}_9\) 的所有可逆元,并分别求出\(\displaystyle \mathbb{Z}_8 \oplus \mathbb{Z}_{25},\mathbb{Z}_{27} \oplus \mathbb{Z}_{49}\) 的可逆元的个数.
- 设 \(\displaystyle \sigma: \overline{x} \longmapsto (\overline{x}, \tilde{\tilde{x}})\) 是 \(\displaystyle \mathbb{Z}_{100}\) 到 \(\displaystyle \mathbb{Z}_4 \oplus \mathbb{Z}_{25}\) 的一个映射.求 \(\displaystyle \mathbb{Z}_4 \oplus \mathbb{Z}_{25}\) 中的元素 \(\displaystyle (\overline{3}, \tilde{\tilde{7}})\) 在 \(\displaystyle \sigma\) 下的原像.
- 求 \(\displaystyle \varphi(100), \varphi(225), \varphi(56),\varphi(60), \varphi(1360), \varphi(420)\).
- 设大于 \(\displaystyle 1\) 的正整数 \(\displaystyle m = p_1^{r_1} p_2^{r_2} \dots p_s^{r_s}\),其中 \(\displaystyle p_1, p_2, \dots, p_s\) 是两两不等的素数.证明：
$\(\displaystyle \varphi(m) = m \left( 1 - \frac{1}{p_1} \right) \left( 1 - \frac{1}{p_2} \right) \dots \left( 1 - \frac{1}{p_s} \right)\)$
- 设 \(\displaystyle \sigma: \overline{x} \longmapsto (\overline{x}, \tilde{\tilde{x}})\) 是 \(\displaystyle \mathbb{Z}_{15}\) 到 \(\displaystyle \mathbb{Z}_3 \oplus \mathbb{Z}_5\) 的一个映射,写出 \(\displaystyle \mathbb{Z}_{15}\) 的每个元素在 \(\displaystyle \sigma\) 下的像.
\(\displaystyle \mathbb{Z}_m\) 的单位群 \(\displaystyle \mathbb{Z}_m^*\),欧拉定理,循环群及其判定
这一节我们来研究 \(\displaystyle \mathbb{Z}_m\) 的可逆元组成的集合 \(\displaystyle \mathbb{Z}_m^*\) 的结构.
问题
写出\(\displaystyle \mathbb{Z}_{12}^*\)的元素,并验证 \(\displaystyle \mathbb{Z}_{12}\) 的加法和乘法是否为 \(\displaystyle \mathbb{Z}_{12}^*\) 的运算.
问题
对\(\displaystyle \mathbb{Z}_m^*\)做如下验证：
（1）\(\displaystyle \mathbb{Z}_m\)乘法是\(\displaystyle \mathbb{Z}_m^*\)的运算；
（2）\(\displaystyle \mathbb{Z}_m\)乘法满足结合律和交换律；
（3）\(\displaystyle \mathbb{Z}_m^*\)中有单位元；
（4）\(\displaystyle \mathbb{Z}_m^*\)中每个元素都有逆元.
这使我们抽象出下述概念：
命题：群
设 \(\displaystyle G\) 是一个非空集合.如果在 \(\displaystyle G\) 上定义了一种代数运算,通常称为乘法,并且它满足下列条件：
(1) \(\displaystyle (ab)c = a(bc), \forall a, b, c \in G\) (结合律)；
(2) \(\displaystyle G\) 中有一个元素 \(\displaystyle \mathrm{e}\) 使得 \(\displaystyle ea = ae = a, \forall a \in G\),称 \(\displaystyle \mathrm{e}\) 是 \(\displaystyle G\) 的单位元；
(3) 对于 \(\displaystyle a \in G\),存在 \(\displaystyle b \in G\),使得 \(\displaystyle ab = ba = \mathrm{e}\),称 \(\displaystyle a\) 可逆,此时称 \(\displaystyle b\) 是 \(\displaystyle a\) 的逆元,记做 \(\displaystyle a^{-1}\),
那么称 \(\displaystyle G\) 是一个群 (group).
如果群 \(\displaystyle G\) 的运算还满足交换律,那么称 \(\displaystyle G\) 是交换群 (或阿贝尔 (Abel) 群).
如果群 \(\displaystyle G\) 只含有有限多个元素,那么称 \(\displaystyle G\) 是有限群；否则称 \(\displaystyle G\) 是无限群.有限群 \(\displaystyle G\) 所含元素的个数称为 \(\displaystyle G\) 的阶,记做 \(\displaystyle |G|\).
在群 \(\displaystyle G\) 中,规定
$\(\displaystyle a^n := \underbrace{aa \dots a}_{n 个}, n \in \mathbb{N}^*\)$
\[\displaystyle a^0 := \mathrm{e}\]
\[\displaystyle a^{-n} := (a^{-1})^n, n \in \mathbb{N}^*\]
容易验证：
$\(\displaystyle a^n a^m = a^{n+m}, \quad (a^n)^m = a^{nm}\)$
其中 \(\displaystyle n, m\) 是任意整数.
在交换群 \(\displaystyle G\) 中,
$\(\displaystyle (ab)^n = a^n b^n, n \in \mathbb{Z}\)$
在非交换群中上面这个式子不成立.
由上面的讨论知道,\(\displaystyle \mathbb{Z}_m^*\) 是有限交换群,称它为 \(\displaystyle \mathbb{Z}_m\) 的单位群.\(\displaystyle \mathbb{Z}_m^*\) 的阶为
\(\displaystyle \varphi(m)\).
问题
对于\(\displaystyle \mathbb{Z}_9\),填写下方的表格,你观察到了什么规律？
| {|c|c|c|c|c|c|}
| \(\displaystyle \overline{a}\) |
\(\displaystyle \overline{a}^2\) |
\(\displaystyle \overline{a}^3\) |
\(\displaystyle \overline{a}^4\) |
\(\displaystyle \overline{a}^5\) |
\(\displaystyle \overline{a}^6\) |
| \(\displaystyle \overline{1}\) |
|
|
|
|
|
| \(\displaystyle \overline{2}\) |
|
|
|
|
|
| \(\displaystyle \overline{4}\) |
|
|
|
|
|
| \(\displaystyle \overline{5}\) |
|
|
|
|
|
| \(\displaystyle \overline{7}\) |
|
|
|
|
|
| \(\displaystyle \overline{8}\) |
|
|
|
|
|
由上表可看出,\(\displaystyle \mathbb{Z}_9^*\) 中每个元素的 \(\displaystyle 6\) 次方都等于 \(\displaystyle \overline{1}\).由此受到启发,猜想有下述结论：
命题
设 \(\displaystyle G\) 是 \(\displaystyle n\) 阶交换群,则对任意 \(\displaystyle a \in G\),有
\(\displaystyle a^n = \mathrm{e}\),其中 \(\displaystyle \mathrm{e}\) 是 \(\displaystyle G\) 的单位元.
证明
设 \(\displaystyle G = \{g_1, g_2, \dots, g_n\}\),其中 \(\displaystyle g_1 = \mathrm{e}\).
任取 \(\displaystyle G\) 的元素 \(\displaystyle g\).为出现 \(\displaystyle g^n\),用 \(\displaystyle g\) 乘 \(\displaystyle G\) 的每个元素得
\(\displaystyle gg_1, gg_2, \dots, gg_n \in G\).
对 \(\displaystyle i \neq j\),假如 \(\displaystyle gg_i = gg_j\),则
\(\displaystyle g^{-1}(gg_i) = g^{-1}(gg_j)\),
从而 \(\displaystyle (g^{-1}g)g_i = (g^{-1}g)g_j\),由此得出\(\displaystyle g_i = g_j\),矛盾.
因此当 \(\displaystyle i \neq j\) 时,\(\displaystyle gg_i \neq gg_j\).
令 \(\displaystyle S = \{gg_1, gg_2, \dots, gg_n\}\),有 \(\displaystyle |S| = n\),而 \(\displaystyle S \subseteq G\),因此 \(\displaystyle S = G\).
故
$\(\displaystyle (gg_1)(gg_2) \cdots (gg_n) = g_1 g_2 \cdots g_n\)$
由于 \(\displaystyle G\) 是交换群,因此可改写上式左侧
\[\displaystyle g^n g_1 g_2 \cdots g_n = g_1 g_2 \cdots g_n\]
两边右乘 \(\displaystyle (g_1 g_2 \cdots g_n)^{-1}\),得 \(\displaystyle g^n \mathrm{e} = \mathrm{e}\).从而
\(\displaystyle g^n = \mathrm{e}\).
命题 \(\displaystyle 1\) 的证明中用到 \(\displaystyle G\) 是交换群这一条件.但这不等于说：当 \(\displaystyle G\) 是非交换群时,命题 \(\displaystyle 1\) 的结论一定不成立.事实上,采用其他的方法可以证明对于非交换群,命题 \(\displaystyle 1\) 的结论也成立.
利用命题 \(\displaystyle 1\) 可以立即得到著名的欧拉定理：
命题：欧拉定理
设 \(\displaystyle m\) 是大于 \(\displaystyle 1\) 的正整数,如果整数 \(\displaystyle a\) 与 \(\displaystyle m\) 互素,那么
$\(\displaystyle a^{\varphi(m)} \equiv 1 \pmod m\)$
证明
由 \(\displaystyle (a, m) = 1\)可得 \(\displaystyle \overline{a} \in \mathbb{Z}_m^*\).
由于 $\displaystyle |\mathbb{Z}_m^*| = \varphi(m)$,据命题1有 $\displaystyle \overline{a}^{\varphi(m)} = \overline{1}$,从而 $\displaystyle \overline{a^{\varphi(m)}} = \overline{1}$.于是
\(\displaystyle a^{\varphi(m)} \equiv 1 \pmod m\).
从问题\(\displaystyle 1.39\)中的表可知：在 \(\displaystyle \mathbb{Z}_9^*\) 中,
\[\displaystyle \overline{2}^6 = \overline{1}, \overline{2}^l \neq \overline{1},\text{当} 1 \leqslant l < 6\]
\[\displaystyle \overline{4}^3 = \overline{1}, \overline{4}^l \neq \overline{1},\text{当} 1 \leqslant l < 3\]
由此受到启发,引出下述概念：
定义 1.7.39
设 \(\displaystyle G\) 是一个群,对于 \(\displaystyle a \in G\),如果存在正整数 \(\displaystyle n\) 使得 \(\displaystyle a^n = \mathrm{e}\),那么称 \(\displaystyle a\) 是有限阶元素,使 \(\displaystyle a^n = \mathrm{e}\) 成立的最小正整数 \(\displaystyle n\) 称为 \(\displaystyle a\) 的阶,记做 \(\displaystyle |a|\)；如果对于任意正整数 \(\displaystyle n\) 都有 \(\displaystyle a^n \neq \mathrm{e}\),那么称 \(\displaystyle a\) 是无限阶元素.
当 \(\displaystyle G\) 是交换群时,常常把 \(\displaystyle G\) 的运算记成加法.此时 \(\displaystyle G\) 的单位元也称为零元,记成 \(\displaystyle 0\)；元素 \(\displaystyle a\) 的逆元称为 \(\displaystyle a\) 的负元,记成 \(\displaystyle -a\)；元素 \(\displaystyle a\) 的 \(\displaystyle n\) 次幂成为 \(\displaystyle a\) 的 \(\displaystyle n\) 倍,记成 \(\displaystyle na\),即 \(\displaystyle na := \underbrace{a + a + \cdots + a}_{n\text{个}}, n \in \mathbb{N}^*\).\(\displaystyle a\) 的 \(\displaystyle 0\) 倍规定为零元,\(\displaystyle (-n)a := n(-a), n \in \mathbb{N}^*\).
问题
写出问题1.39中\(\displaystyle \mathbb{Z}^*_9\)各元素的阶.你发现了什么
由此猜测有下述结论：
命题
群 \(\displaystyle G\) 中,如果元素 \(\displaystyle a\) 的阶为 \(\displaystyle n\),那么
$\(\displaystyle a^m = \mathrm{e} \iff n \mid m\)$
证明
充分性: 设 \(\displaystyle n \mid m\),则 \(\displaystyle m = kn,k\in\mathbb{Z}\),于是
\(\displaystyle a^m = a^{kn} = (a^n)^k = \mathrm{e}^k = \mathrm{e}\).
必要性: 设 \(\displaystyle a^m = \mathrm{e}\).对 \(\displaystyle m\) 和 \(\displaystyle n\) 作带余除法：
\[\displaystyle m = kn + r, 0 \leqslant r < n\]
则
\(\displaystyle \mathrm{e} = a^m = a^{kn + r} = a^{kn} a^r = a^r\).
由于 \(\displaystyle a\) 的阶为 \(\displaystyle n\),因此 \(\displaystyle r = 0\).从而 \(\displaystyle n \mid m\).
从问题1.39的表中可以发现：在 \(\displaystyle \mathbb{Z}_9^*\) 中,$\(\displaystyle \overline{2}^2 = \overline{4}, \overline{2}^3 = \overline{8}, \overline{2}^4 = \overline{7}, \overline{2}^5 = \overline{5}, \overline{2}^6 = \overline{1}\)$
因此 $\(\displaystyle \mathbb{Z}_9^* = \{\overline{2}, \overline{2}^2, \overline{2}^3, \overline{2}^4, \overline{2}^5, \overline{2}^6\}\)$
由此受到启发,引出下述概念：
定义 1.7.41（循环群）
如果群 \(\displaystyle G\) 中有一个元素 \(\displaystyle a\),使得 \(\displaystyle G\) 的每一个元素都能写成 \(\displaystyle a\) 的方幂的形式,那么称 \(\displaystyle G\) 是循环群,把 \(\displaystyle a\) 叫做 \(\displaystyle G\) 的一个生成元,此时可以把 \(\displaystyle G\) 记成 \(\displaystyle \langle a \rangle\).
问题
回答下述问题：
（1）\(\displaystyle \mathbb{Z}_9^*\)是不是循环群？如果是,请写出它的所有生成元；
（2）设 \(\displaystyle G\) 是有限群,如果 \(\displaystyle G\) 中有一个元素 \(\displaystyle a\),使得 \(\displaystyle a\) 的阶等于 \(\displaystyle |G|\),那么 \(\displaystyle G\) 是循环群,\(\displaystyle a\) 是 \(\displaystyle G\) 的一个生成元；
（3）设 \(\displaystyle G\) 是有限循环群,则 \(\displaystyle a\) 是 \(\displaystyle G\) 的生成元当且仅当 \(\displaystyle a\) 的阶等于 \(\displaystyle |G|\).
（4）循环群一定是交换群吗？交换群一定是循环群吗？
- 写出 \(\displaystyle \mathbb{Z}_{18}^*\) 的所有元素,并且计算每两个元素的乘积.
- 分别计算 \(\displaystyle \mathbb{Z}_{13}^*, \mathbb{Z}_{24}^*\) 的每个元素的 \(\displaystyle l\) 次方,\(\displaystyle 1 \leqslant l \leqslant 8\),并且说出每个元素的阶是多少？
- 设 \(\displaystyle n = 17 \times 23, a = 3\),求正整数 \(\displaystyle b (b < n)\),使得
\(\displaystyle ab \equiv 1 \pmod{\varphi(n)}\).
- 在第 3 题中,设 \(\displaystyle \overline{x} \in \mathbb{Z}_n^*\),证明：\(\displaystyle \overline{x}^{ab} = \overline{x}\).
- 分别求出循环群 \(\displaystyle \mathbb{Z}_7^*, \mathbb{Z}_{11}^*\) 的所有生成元.
- 分别求出循环群 \(\displaystyle \mathbb{Z}_{13}^*, \mathbb{Z}_{17}^*, \mathbb{Z}_{19}^*\) 的生成元的个数.
- \(\displaystyle \mathbb{Z}_{18}^*\) 是不是循环群？如果是,它的一个生成元是什么？求 \(\displaystyle \mathbb{Z}_{18}^*\) 的每个元素的阶,并且写出它的所有生成元.
- \(\displaystyle \mathbb{Z}_{27}^*\) 是不是循环群？如果是,求出它的所有生成元.
- 利用欧拉定理证明费马小定理.
- 群 \(\displaystyle G\) 中,元素 \(\displaystyle a\) 的阶为 \(\displaystyle n\),证明：对于任意整数 \(\displaystyle k\),有
\(\displaystyle |a^k| = \frac{n}{(n, k)}\).
- 群 \(\displaystyle G\) 中,设 \(\displaystyle a, b\) 的阶分别为 \(\displaystyle n, m\),且 \(\displaystyle ab = ba\),且 \(\displaystyle (n, m) = 1\),证明： \(\displaystyle ab\) 的阶等于 \(\displaystyle nm\).
- 设 \(\displaystyle G\) 为有限交换群,证明： \(\displaystyle G\) 中有一个元素的阶是其他元素的阶的倍数.
- 设\(\displaystyle S\subseteq \mathbb{C}\)是有限集，满足\(\displaystyle |S|=k\)且对任意\(\displaystyle a,b\in S\)有\(\displaystyle ab\in S\)。
- 求证：\(\displaystyle \forall a\in S:a^k=1\)；
- 求\(\displaystyle S\)中所有元素之和。
拓展阅读：英雄时代的落幕
数学,一个不需要现实实验验证,仅靠一张纸和一支笔,就能在逻辑推演中,构建出完整理论体系的学科,竟然能一路从结绳记事发展到今天这个样子,既然这就是数学的特性,所有定理和概念都能一步步往前找到理论来源,而且不用操心现实因素,那所有学过数学的人,脑子里就会自然而然出现一个观念,我们可不可以用一套完备而自洽的数学语言,把全部数学知识和数学问题都完整的表达组织并证明呢,数学家说,哎,你不能光盯着那些抽象概念而不把地基打牢,大放厥词啊,那至少一加一等于二,这种自然数算术问题的底层基础,不可能混乱吧,是不可能混乱吧是不可能混乱吧,各位不要慌,自然数算术的地基,当然不会混乱,它根本从来就没有过地基,被这100年来的,这种将整个数学视为逻辑延伸的观念,成为了我们今天要说的20世纪数学危机中,登场的第一个也是思想最悠久的派系,逻辑主义,
那想让逻辑主义者的目标真正达成,首先就要确保目前数学里各个领域不存在模棱两可的悖论,罗素从小就崇拜康托尔和他的集合论,但罗素长大之后,发现了朴素集合论里,有着一个明显的悖论,如果有一个集合,它的元素是所有不包含自身的集合,那么这个集合自身是否属于它的元素
罗素为了方便给外行人解释这个悖论,还用了理发师做过例子,这种悖论会出现的根本原因,就是它产生了一种叫做自指的现象,一个命题在否定它自身,最简单的表述就是,我这句话是错的,这种悖论是不可能通过逻辑学内部定律和推导消除的,如何解决这种简单粗暴的悖论呢？答案可能出乎大家意料,罗素悖论本身根本就不是什么大事,光罗素自己一个人就提出了好几种消除它的方式,自指设的问题不就出在自己会指自己吗,我们直接规定不能指不就行了吗。罗素提出的其中一个方法叫做类型论,就是给对象分层,只有更高一层的东西可以指低层的东西,不准同层互指。同在20世纪早期的策梅洛和弗伦克尔,还借着解决罗素悖论的这个由头,把康托尔的朴素集合论整理成了公理化集合论,这个名字以策梅洛和弗伦克尔的名字首字母命名,简称ZF,再加上后来融入的选择公理,叫作 ZFC 公理系统。这个系统其实是一个毫无数学美感的东西,它就像一堆不相关的砖头砌成的一堵墙,每个砖头分别是一个公理,同时这些公理分别都在防止一些问题的产生,以及确保约定的合法,比如这个C砖头本来就是一个无法证明,且当时很多人不接受的观点,但是策梅洛发现没它很麻烦,所以咔一下就气上来了,变成一个公理,所以这堵墙只有你接不接受的问题,没有什么证明它对不对的问题,这个系统就是目前现代数学,最广泛接受的默认基础,从幼儿园到研究生的数学教育,都是在承认它的前提上进行的,虽然依然有不完美的地方,但已经是如今数学,兼顾全局下的最佳选择了,ZFC这个规则外,也直接通过一条分离公理,强行禁止了罗素悖论的构造,所以这个悖论本身,到这里已经没有什么存在感了。
20世纪发生过一场影响深远的数学危机,它将导致数学界长期被分裂成三个阵营。逻辑主义希望将过往几千年数学成果纳入一个极端复杂的逻辑体系，它的这一努力在数学界遇到的最成建制的反对者就是直觉主义,他们被称为一群激进而纯粹的疯子。直觉主义的精神来源可以追溯到克罗内克,虽然他在各种讲述集合论的历史科普中都扮演着一个彻头彻尾的反面龙套,但他在学术上,他在代数和数论领域非常强大,他打压康托尔也主要是因其从始至终都无法接受无穷集合的存在,克罗内克的观点后来被布劳威尔所继承。直觉主义认为，数学是人类心智的活动,只有人类心智所能把握能构造的对象才算真正的数学对象,19世纪下半叶以来,数学变得越来越像是逻辑和符号的游戏,康托尔把实无穷作为一个客观存在的数学对象,击穿了他们内心最后的防线,更别说接受拿无穷大去比较大小了。理由可以归结为一句质问,闭上眼睛,你觉得你的大脑真的能想象出来,宇宙中有无穷多个星体这句话吗,你哪怕有再丰富的想象力,你的心智所能把握的场景也只是成千上万,最多是一后面跟几十上百个零,但是你不可能真正的感知出实无穷,直觉主义另一个旗帜鲜明的立场是,他们不接受对涉及无穷的问题证明中,仅用反证法来证明某物存在,也就是说他们不接受非构造性的证明。
传统的数学里一直有一个不可撼动的逻辑定律,叫做排中律,即一个命题要么为真,要么为假,不存在第三种情况,反证法即是脱胎于此规律。直觉主义者不允许使用排中律来证明涉及无穷的存在性问题,难道数学命题可以是真或假以外的第三种状态吗,他们说：“可以。排中律预设了命题从诞生那天开始就具备一个明确的真假性。”在涉及无限对象的问题中,应该存在这样一种命题,在构造性证明出现之前,没人有权断言它的真假性,不知道本身是一种合法的数学状态。承认一些命题就是未知的,以及抵制排中律这两件事,还像话吗,回忆一下我们从小到大,数学这门课贯彻一个什么思想。于是第三个派系正式出现了,以希尔伯特为核心的形式主义,也是三股势力里最强大的派系。希尔伯特认为：“禁止数学家用排中律,就像在拳击比赛中禁用拳头一样。”
本着敌人的敌人,就是朋友的观点,希尔伯特和罗素的工作,几乎能归到同一个阵营里,但希尔伯特还是非常明确的和逻辑主义划清了借鉴和罗素的工作几乎跪到同一个阵营里但希尔伯特还是非常明确的,和逻辑主义划清了借鉴,因为罗素的野性,是要把数学彻底还原到逻辑层面上,一下一等于二这种东西,都不应该被当作原始对象,但希尔伯特自认为,自己没有那么魔争,他只要证明,整个数学是确定且一致的,就可以了,所以希尔伯特就像一个,16到19世纪常见的,有神论科学家一样,相信有一套最高的法则在天上,但是各种科学实验还是要在学科领域内讨论的,但罗素在这里就像一个神学家,他试图要把所有物质所有定律,全都一路还原到他们全是上帝创造的。希尔伯特觉得没必要把逻辑学放到万物本源那个地位,所以当时的数学界就形成了,这样一种三足鼎立的状态,这三个势力没一个省油的灯,但是当年确实存在势力上的不对等,当时的希尔伯特,已经不是年轻的时候,只能看着前辈康托尔,受克罗内克欺负而无能威力的年轻人了,他现在已经成长为德国乃至整个欧洲地区的数学霸主了,而且就是在我们熟悉的哥廷根大学
所以直觉主义与逻辑和形式主义的争论,在数学史上又被称为布劳威尔—希尔伯特之争,虽然无论是希尔伯特,还是此刻大部分的观众朋友,都觉得直觉主义坚持的立场很没道理,其实他们也有苦衷,因为如果真的让逻辑主义和形式主义,为所欲为,接受存在但不可构造的对象的话,数学就会出现很多,现实世界无法接受的结论,比如前文提到的选择公理,选择公理,它会导致巴拿赫—塔斯基悖论,这个悖论简要说就是,集合论能够证明出存在一种方式,但是给不出这种方式,把一个普通的三维实心球进行切割,平移和旋转,变成两个和原来大小密度质量,完全一样的实心球,数学里是完全成立的,如果这事真能做到我们就可以把一颗石子变成一 实心球数学里是完全成立的如果这事真能做到,我们就可以把一颗石子,变成一颗星球了,直觉主义者认为,这就是把数学,仅仅当做纯粹的逻辑与符号游戏要付出的代价,问题在于,如果数学真的和现实世界毫无关系,只是一套自我封闭的符号系统,那么就很难解释这样一个历史事实,自中世纪以来,数学为什么能在力学,天文学,电磁学,乃至现代物理的发展中,反复展现出惊人的有效性,所以说,直觉主义者并非单纯的反对逻辑或形式化,而是在提醒所有人,数学之所以有存在的必要,能成为科学里有意义的语言,恰恰是因为,它在某种程度上,仍然保留着与人类直觉,构造过程,以及现实可操作性的联系,而且也正是希尔伯特本人,在他著名的23个问题中,也留下了一个与此密切相关的要求,希尔伯特第六问题要求将物理学公理化,用严格的数学公理体系为物理学奠基,这个问题本身恰恰默认了一个前提,数学并不是一套与现实毫无关联的纯符号游戏,而应该能够为现实世界的基本规律,提供清晰、稳定且可理解的结构框架,这才是第三次数学危机真正的分歧点——一场关于数学为何存在,未来又要走向何处的深刻反思,各个阵营在这场持续的争论和对抗中,不断催生出各种新的思想与技术成果,而它对现代数学发展所造成的最直观的影响,却不是在数学范畴里,甚至不是在科学范畴里,只是一个社会学层面的改变。
在20世纪初,数学领域里正式出现了具有核心领袖和共同纲领的学派。虽然必须承认数学是一个依赖于天才推动的学科,但只寄希望于可遇不可求的天才来推动一个地区或民族的数学视野是不可能的。试想，如果牛顿在没有费马巴罗和加利略开普勒指引的情况下,以近乎从零开始的状态,独自一个人写出了数学原理,但他的身后没有大学,没有皇家学会,同时也没有任何一个普通的数学家,也许不出一代人,整个欧洲就没有人能看懂这本书,这些晦涩的数学推导不久就将失传,牛顿的出身与否对欧洲的数学发展将不会有任何影响,最多是在几百年后被人
到了19世纪末,数学的复杂性已经不再允许一个人通晓它的全部领域,数学研究不可避免的走向分工与协作,在第三次数学危机的历史背景下,希尔伯特在哥廷根系统性地组织起一个现代意义上的数学共同体,即后来的哥廷根学派。此前近200年的数学史几乎被英法两国所垄断,而在希尔伯特的推动下,数学研究的重心逐渐转移到德国,高斯和黎曼固然是划时代的天才,但真正具有历史决定性意义的,是一个成建制可持续运作的学派,他不再完全依赖于天才的出现,而是拥有持续生产,改变数学面貌之人的能力。希尔伯特为了稳固德国在世界数学版图中的话语权,团结了一切可以团结的力量,他呼吁放下民族与性别的偏见,把注意力重新集中在数学问题上,正是在希尔伯特这样的理念支持下,历史上最伟大的女数学家诺特才得以在重重制度性阻碍下进入数学界核心,尽管她因学术界深入骨髓的性别歧视长期无法获得正式教职,但她的成就的重要性并未因此而减弱,她在理论物理中提出了诺特定理,第一次从严格的数学层面揭示了对称性与守恒定律之间的深刻对应关系,成为了现代物理最底层的核心之柱。诺特并不仅仅是一位天才的个体,围绕她形成的研究共同体——诺特学派,培养出了一大批深刻影响20世纪数学走向的数学家,它使得抽象代数从一门零散的技巧集合成长为一套高度统一的理论体系,诺特是真正意义上的抽象代数之母,伽罗瓦和阿贝尔是我们前文所述的那种不世出的天才,而艾米·诺特是将抽象代数学科化建制化的第一人。
然而好景不长,第一次世界大战所造成的深层社会创伤在停战后的20年间持续发酵,使德国乃至整个欧洲社会逐步走向一种难以调和的紧张局面。1933年，希特勒上台,纳粹随即开始在国内进行种族清洗,同年4月13日,哥廷根数学世界的乌托邦时代宣告结束,包括诺特在内的大量学者在纳粹的迫害下流亡海外,希尔伯特竭力维护哥廷根的学术传统,却依然无力回天。在时代的暴力面前,再伟大的学者也只是历史巨轮下微小而无助的个体,清洗一年之后,重病在身的希尔伯特参加了一场德国政界的宴会,学术清洗的始作俑者之一,纳粹德国的教育部长鲁斯特问希尔伯特：“哥廷根数学研究所真的因为这场清洗而遭受很大损失吗？”
希尔伯特回答道：“受损？它已经不存在了。”
希尔伯特于二战期间去世，他去世时,哥廷根大学已经在纳粹的控制下全面重组,曾经的哥廷根学派也不复存在。希尔伯特葬礼的出席者不足十人,直到数月之后,其他国家的数学家们才陆续得知,这位20世纪初世界数学中心的缔造者,竟然在无人知晓的情况下,死在了他曾亲手建设并寄予厚望的哥廷根。
希尔伯特出生于东普鲁市省的哥尼斯堡,这里是欧拉研究图论\footnote{即哥尼斯堡七桥问题。}的起源地,同时也是康德的故乡。康德出生的时代,数学在解释世界如何运作这个问题上,获得了前所未有的成功,但另一方面,形而上学却陷入了无休止的争论.康德发现,围绕某些问题所形成的两种不同的理论和学说,在同样的理性框架下各自成立,但却相互矛盾,比如假设宇宙的时间有一个开端,那么开端之前,就不会存在变化,也就不可能有动机,去产生这样的第一刻,但是如果宇宙的时间,没有开端,那就意味着,在现在之前已经过去了无限长的时间,但无限长的时间不可能一步一步走完,所以现在不可能到达,这种通过理性推导出两种对立结论的现象叫做二律背反,康德敏锐地意识到,出现这种问题的原因是人们滥用了自己的理性,于是他写下了纯粹理性批判,第一次系统地划定了理性的边界,向人们宣布,人类的认知能力具有不可逾越的节骨心限制,这个世界上有些超越经验的问题,人的理性是无法认知的。
一百多年后,希尔伯特站在了康德的对立面,在他所处的时代,人类改造和认识世界的能力已远非康德时代所能想象。康德为理性划定了不可逾越的边界,希尔伯特纲领则试图证明这种边界在数学中并不存在。他在柯尼斯堡演讲的最后，坚定有力地说出来最后一句话
Wir müssen wissen, wir werden wissen.
我们必须知道，我们必将知道。
然而，生命并不总是以伟大而有决定意义的诗句告终的。
几乎在希尔伯特发表柯尼斯堡演讲的同时，有一项研究工作完成了，其作者叫哥德尔，这一工作证明了希尔伯特纲领在原则上不可能成立,其结论被称为哥德尔不完备定理,从罗素悖论可以得知，击碎一个逻辑体系的最简便方式就是建立自指问题,但数学问题在现实语境中总会被模糊的语意和新的规约所消解,所以哥德尔帮希尔伯特完成了一个工作,他把推理和命题本身变成了可以被数学精确处理的对象。所有的数学命题都可以写成符号形式,哥德尔给每个符号指派了一个自然数作为其编码,为了确定这几个数字的位置,哥德尔把这几个符号的编码,依次放在从二开始的质数的乘方上,最后把它们乘起来,因为一个数字的质因数分解是唯一的,所以这个大数在技术上,可以和质数乘方的乘积等价替换,这种和命题一一对应的天文数字叫做哥德尔数,它第一次让数学里的所有命题落入了只由自然数构成的世界之中,到这一步为止,所有事情的发展都在希尔伯特的设想之中,每一个命题都被分配了一段和它自身意义无关的身份编码,命题在一边,数字在另一边,两者互不干扰,只要这种关系不被打破,数学就仍然是安全的，不能让某一个命题在系统内部说出属于他自己的那串编号,因为一旦发生这种情形,命题就不再只是被描述的对象,而会开始参与对自身的判断,希尔伯特极力避免的情形,恰恰是哥德尔这篇论文,真正的致命一击。在经过一系列极端繁琐而谨慎的形式构造后,哥德尔最终在论文里写下了一条,叫做17 Gen r的命题,希尔伯特竭力回避的噩梦,终于在这个系统内部合法的降临,一个命题在镜子里看到了自己,哥德尔数等于计的命题无法被证明,这一命题,他自己的哥德尔数等于计哥德尔就此证明这一命题他自己的哥德尔数等于计,哥德尔就此证明了,任何一个一致的形式系统,只要其表达能力足以涵盖皮亚诺算术,就可以在其中构造,在体系中不能被证明的真命题,因此,通过推理演绎,不能得到所有真命题,哥德尔不完备定理,以及随后相继出现的,第二不完备定理,与图灵关于不可判定性的工作,从根本上击碎了希尔伯特纲领的哲学构想,而且这种崩塌,并不单独来自于宏大的理论,而是全方位的事实冲击,其中最具象征意义的例子,正是希尔伯特在1900年,提出的第一个问题,连续统假设。1940年,哥德尔证明了连续统假设与ZFC公理系统的相对一致性,即如果ZFC本身是一致的,那么在ZFC中无法证明连续统假设是错误的。1963年,科恩进一步证明了连续统假设无法由ZFC推导成立,由此,连续统假设成为了一个在ZFC框架内永远无法证明的问题。
以20世纪中叶希尔伯特时代的终结为分水岭,20世纪前后的两段数学史,就像在两个遥远而陌生的世界之中所发生的故事,此前的数学世界仍深陷于关于基础,本体论与合法性的哲学争论,但随着学科的成熟与分化,哲学观念与宗教式的狂热逐渐从现代数学研究中退场,第三次数学危机以没有任何一方胜利的结局而告终。
魔笛手那甜蜜的笛声似乎永远停息了。但是，整个世界遍布着希尔伯特的学生，以及希尔伯特学生的学生。赫尔曼·外尔正以他特有的热情，试图把普林斯顿高等研究所办成另一个伟大的充满热情的科学中心——要像他年轻时所在的哪个哥廷根一样。在纽约，库朗被安置在一所废弃不用的帽子工厂里，朋友们风趣地把这个地方叫做“库朗研究所”，在这里，希尔伯特的精神也同样闪耀着。
现代数学不再只在欧洲少数城市内部传承,而是开始真正成为一项全球性的事业。这之后的数学分支,已经复杂到,任何人都无法通晓全貌,欧拉和高斯那种全才式的英雄时代已经彻底结束,高度抽象的现代数学,除了个人天赋之外,更依赖长期,稳定,系统性的智力投入,它没有时空和资源上的限制,没有人种和性别上的垄断,作为一个没有入门条件,却有着最高智慧门槛的学科,它真正需求的成本,只有持续的思考,以及为之付出的心血。
A 组习题
B 组习题
C 组习题
杂\(\displaystyle \quad\)题
-
【2020全国II卷12】 若序列 \(\displaystyle a_1 a_2 \cdots a_n \cdots\) 满足 \(\displaystyle a_i \in \{0, 1\} (i = 1, 2, \cdots)\),且存在正整数 \(\displaystyle m\),使得 \(\displaystyle a_{i+m} = a_i (i = 1, 2, \cdots)\) 成立,则称其为 0-1 周期序列.并称满足 \(\displaystyle a_{i+m} = a_i (i = 1, 2, \cdots)\) 的最小正整数 \(\displaystyle m\) 为这个序列的周期.对于周期为 \(\displaystyle m\) 的 0-1 序列 \(\displaystyle a_1 a_2 \cdots a_n \cdots\),\(\displaystyle C(k) = \frac{1}{m} \sum_{i=1}^m a_i a_{i+k} (k = 1, 2, \cdots, m - 1)\) 是描述其性质的重要指标.下列周期为 \(\displaystyle 5\) 的 0-1 序列中,满足 \(\displaystyle C(k) \leqslant \frac{1}{5} (k=1,2,3,4)\) 的序列是
- \(\displaystyle 11010 \cdots\)
- \(\displaystyle 11011 \cdots\)
- \(\displaystyle 10001 \cdots\)
- \(\displaystyle 11001 \cdots\)
答案
C.
- 【2007福建文16理16】（多选）中学数学中存在许多关系，比如“相等关系”、“平行关系”等，如果集合\(\displaystyle A\)中的元素之间的一个关系“\(\displaystyle \sim\)”满足以下三个条件：
（1）自反性：对于任意\(\displaystyle a\in A\)，都有\(\displaystyle a\sim a\)；
（2）对称性：对于\(\displaystyle a,b\in A\)，若\(\displaystyle a\sim b\)，则有\(\displaystyle b\sim a\)；
（3）传递性：对于\(\displaystyle a,b,c\in A\)，若\(\displaystyle a\sim b,b\sim c\)，则有\(\displaystyle a\sim c\)，
则称“\(\displaystyle \sim\)”是集合\(\displaystyle A\)的一个等价关系。下列关系中，是等价关系的有
3. 【2019命题标准样题15改编】（多选）要合理地刻画三角形三个顶点的“集中程度”,可以使用
- 三角形的周长
- 三角形的面积
- 三角形的外接圆半径
- 三角形的最大边长
答案
AD.
-
【2021新高考II卷12】 （多选）设正整数 \(\displaystyle n = a_0 \cdot 2^0 + a_1 \cdot 2^1 + \cdots + a_{k-1} \cdot 2^{k-1} + a_k \cdot 2^k\),其中 \(\displaystyle a_i \in \{0, 1\}, i = 0, 1, 2, \dots, k\).记 \(\displaystyle \omega(n) = a_0 + a_1 + \dots + a_k\),则
-
\(\displaystyle \omega(2n) = \omega(n)\)
- \(\displaystyle \omega(2n + 3) = \omega(n) + 1\)
- \(\displaystyle \omega(8n + 5) = \omega(4n + 3)\)
- \(\displaystyle \omega(2^n - 1) = n\)
答案
ACD.\(\displaystyle \omega(n)\)指的是10进制数\(\displaystyle n\)对应的二进制序列中1的个数，记十进制数\(\displaystyle n\)的二进制表示为\(\displaystyle B(n)=(a_0a_1\cdots a_k)_2\).对于A，\(\displaystyle 2n\) 的二进制序列相当于将\(\displaystyle n\)的二进制序列左移一位，末尾添一个 \(\displaystyle 0\)，所以\(\displaystyle \omega(2n)=\omega(n)\)，A正确。对于B，当\(\displaystyle n=3\)时，\(\displaystyle \omega(2n+3)=2,\omega(n)+1=3\)，二者不相等，故B错误。
对于C，分别将$\displaystyle 8n+5$ 与 $\displaystyle 4n+3$写成二进制形式：
$$\displaystyle B(8n+5)=(\underbrace{\cdots\cdots}_{n\text{的二进制表示}}101)_2,\quad B(4n+3)=(\underbrace{\cdots\cdots}_{n\text{的二进制表示}}11)_2,$$
可知$\displaystyle \omega(8n+5)=\omega(4n+3)=\omega(n)+2$.C正确。
$\displaystyle 2^n-1$ 的二进制表示是 $\displaystyle n$ 个 $\displaystyle 1$，所以$\displaystyle \omega(2^n-1)=n$，D错误。
- 【2014北京8】学生的语文、数学成绩均被评定为三个等级, 依次为“优秀”“合格”“不合格”. 若学生甲的语文、数学成绩都不低于学生乙, 且其中至少有一门成绩高于乙, 则称“学生甲比学生乙成绩好”. 如果一组学生中没有哪位学生比另一位学生成绩好, 并且不存在语文成绩相同、数学成绩也相同的两位学生, 则这一组学生最多有多少个？
答案
3.
为方便起见, 把优秀、合格、不合格记为\(\displaystyle 3,2,1\)分. 由于不存在语文成绩相同、数学成绩也相同的学生, 所以最多只可能有9个学生, 我们可以把所有可能的学生列出来:
$\(\displaystyle \begin{matrix} P_{33} & P_{32} & P_{31} \\ P_{23} & P_{22} & P_{21} \\ P_{13} & P_{12} & P_{11} \end{matrix}\)$
其中学生\(\displaystyle P_{ij}\)表示语文是\(\displaystyle i\)分, 数学是\(\displaystyle j\)分. 我们逐步排除掉不可能出现的学生.
因为一组学生中没有哪位学生比另一位学生成绩好, 所以不可能有\(\displaystyle P_{33}\)和\(\displaystyle P_{11}\)(一定是最好或最差). 根据对称性, 接下来只需考虑\(\displaystyle P_{32}\)和\(\displaystyle P_{31}\)是否存在.
如果有\(\displaystyle P_{32}\), 则不可能有\(\displaystyle P_{31},P_{22},P_{21},P_{12}\), 必须有\(\displaystyle P_{23}\)或\(\displaystyle P_{13}\)(不可能都有), 此时这一组学生最多只有2个, 为\(\displaystyle \{P_{32},P_{23}\}\)或\(\displaystyle \{P_{32},P_{13}\}\).
如果有\(\displaystyle P_{31}\), 则不可能有\(\displaystyle P_{21}\)和\(\displaystyle P_{32}\). 所以这一组学生人数最多的情况只可能是\(\displaystyle \{P_{31},P_{22},P_{13}\}\).
综上, 这一组学生最多有3个.
- 【2017北京文14】某学习小组由学生和教师组成, 人员构成同时满足以下三个条件:
（1）男学生人数多于女学生人数;
（2）女学生人数多于教师人数;
（3）教师人数的两倍多于男学生人数.
若教师人数为4, 则女学生人数的最大值为\(\displaystyle (\triangle)\);该小组人数的最小值为\(\displaystyle (\triangle)\).
答案
6;12.
设男学生人数为\(\displaystyle a\), 女学生人数为\(\displaystyle b\), 教师人数为\(\displaystyle c\). 由条件, \(\displaystyle a\geqslant b+1\), \(\displaystyle b\geqslant c+1\), \(\displaystyle 2c\geqslant a+1\).
若教师人数为4, 则\(\displaystyle a+1\leqslant 2c=8\), \(\displaystyle a\leqslant 7\), \(\displaystyle b\leqslant a-1=6\). 而当\(\displaystyle b=6\)时, \(\displaystyle a=7,c=4\)满足三个条件. 故女学生人数最大值为6.
\(\displaystyle a+b+2c\geqslant (b+1)+(c+1)+(a+1)\), 因此\(\displaystyle c\geqslant 3\), 从而\(\displaystyle b\geqslant 4, a\geqslant 5\). 当\(\displaystyle c=3,b=4,a=5\)时, 满足三个条件. 故小组人数最小值为12.
- 【2009江西3】 已知全集\(\displaystyle U=A\cup B\)中有\(\displaystyle m\)个元素,\(\displaystyle (\complement_UA)\cup(\complement_UB)\)中有\(\displaystyle n\)个元素. 若\(\displaystyle A\cap B\)非空, 求\(\displaystyle A\cap B\)的元素个数。（用\(\displaystyle m,n\)表示）
答案
\(\displaystyle m-n\)
由德摩根律，\(\displaystyle (\complement_UA)\cup(\complement_UB)=\complement_U(A\cap B),\)
因而
$\(\displaystyle n=|\complement_U(A\cap B)|=|U|-|A\cap B|=m-|A\cap B|．\)$
即\(\displaystyle |A\cap B|=m-n\)。
- 【2015广东文10】已知集合
$\(\displaystyle \begin{aligned} E&=\{(p,q,r,s)|0\leqslant p < s\leqslant 4, 0\leqslant q < s \leqslant 4, 0\leqslant r < s\leqslant 4\text{且}p,q,r,s\in\mathbb{N}\} \\ F&=\{(t,u,v,w)|0\leqslant t < u\leqslant 4, 0\leqslant v < w\leqslant 4\text{且}t,u,v,w\in\mathbb{N}\}, \end{aligned}\)$
求\(\displaystyle |E|+|F|\).
答案
200.
- 【2012安徽10】
6位同学在毕业聚会活动中进行纪念品的交换，任意两位同学之间最多交换一次，进行交换的两位同学互赠一份纪念品，已知6位同学之间共进行了13次交换，求收到4份纪念品的同学人数。
答案
2或4.
- 【2011陕西14】植树节某班 20 名同学在一段直线公路一侧植树，每人植一棵，相邻两棵树的距离是 \(\displaystyle 10\)．开始时需将树苗集中放置在某一树坑旁边，使每位同学从各自树坑出发前来领取树苗往返所走的路程总和最小，求该最小值．
答案
2000.
设树苗放在第 \(\displaystyle k\) 棵树下，用 \(\displaystyle a_n\) 表示第 \(\displaystyle n\) 棵树与第 \(\displaystyle k\) 棵树的距离，则 \(\displaystyle a_n=10|n-k|\)，其中 \(\displaystyle n=1,2,\cdots,20\)． 所以往返路程总和为
$\(\displaystyle \begin{aligned} 2\sum\limits_{n=1}^{20}10|n-k| &=20\sum\limits_{n=1}^k(k-n)+20\sum\limits_{n=k+1}^{20}(n-k) \\ &=20\dfrac{(k-1)k}{2}+20\dfrac{(21-k)(20-k)}{2} \\ &=10(2k^2-42k+420). \end{aligned}\)$
函数 \(\displaystyle y=2x^2-42x+420\) 的对称轴是直线 \(\displaystyle x=\dfrac{21}{2}\)，但是 \(\displaystyle k\) 是正整数，所以当 \(\displaystyle k=10\) 或 \(\displaystyle k=11\) 时往返路程取最小值 \(\displaystyle 2000\)．
- 【2015年新题型测试】
甲、乙、丙、丁四人商量去看电影.
甲说：乙去我才去；乙说：丙去我才去；丙说：甲不去我就不去；丁说：乙不去我就不去.最后有人去看了电影，有人没去看电影，去的人是谁？
- 【2023四省联考15】数学家祖冲之曾经给出圆周率 \(\displaystyle \pi\) 的两个近似值：“约率” \(\displaystyle \frac{22}{7}\) 与“密率” \(\displaystyle \frac{355}{113}\)．它们可用“调日法”得到：称小于 \(\displaystyle 3.1415926\) 的近似值为弱率,大于 \(\displaystyle 3.1415927\) 的近似值为强率．由 \(\displaystyle \frac{3}{1} < \pi < \frac{4}{1}\),取 \(\displaystyle 3\) 为弱率,\(\displaystyle 4\) 为强率,得 \(\displaystyle a_{1} = \frac{3+4}{1+1} = \frac{7}{2}\),故 \(\displaystyle a_{1}\) 为强率,与上一次的弱率 \(\displaystyle 3\) 计算得 \(\displaystyle a_{2} = \frac{3+7}{1+2} = \frac{10}{3}\),故 \(\displaystyle a_{2}\) 为强率,继续计算,\(\displaystyle \cdots\cdots\)．若某次得到的近似值为强率,与上一次的弱率继续计算得到新的近似值；若某次得到的近似值为弱率,与上一次的强率继续计算得到新的近似值,以此类推．已知 \(\displaystyle a_{m} = \frac{22}{7}\),则 \(\displaystyle m = (\triangle)\) ；\(\displaystyle a_{8} = (\triangle)\)．
答案
6;47/15,列表如下：
<div align="center" markdown>
\renewcommand{\arraystretch}{1.8}
| {c|cccccccc}
\Xhline{1pt}
序号 | \(\displaystyle a_1\) | \(\displaystyle a_2\) | \(\displaystyle a_3\) | \(\displaystyle a_4\) | \(\displaystyle a_5\) | \(\displaystyle a_6\) | \(\displaystyle a_7\) | \(\displaystyle a_8\) |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| \Xhline{1pt}
分数 | \(\displaystyle \frac{3+4}{1+1}\) | \(\displaystyle \frac{3+7}{1+2}\) | \(\displaystyle \frac{3+10}{1+3}\) | \(\displaystyle \frac{3+13}{1+4}\) | \(\displaystyle \frac{3+16}{1+5}\) | \(\displaystyle \frac{3+19}{1+6}\) | \(\displaystyle \frac{3+22}{1+7}\) | \(\displaystyle \frac{22+25}{7+8}\) |
| 近似值 | \(\displaystyle \frac72\) | \(\displaystyle \frac{10}{3}\) | \(\displaystyle \frac{13}{4}\) | \(\displaystyle \frac{16}{5}\) | \(\displaystyle \frac{19}{6}\) | \(\displaystyle \frac{22}{7}\) | \(\displaystyle \frac{25}{8}\) | \(\displaystyle \frac{47}{15}\) |
| 强弱率 | 强率 | 强率 | 强率 | 强率 | 强率 | 强率 | 弱率 | 弱率 |
| \Xhline{1pt} | | | | | | | | |
已知甲同学第一个报数,当五位同学依序循环报到第100个数时,求五位同学拍手的总次数与甲同学拍手的总次数.
i.\(\displaystyle x_1 = y_1 = 1\)，\(\displaystyle x_m = n\)，且 \(\displaystyle S\) 中的向量互不相等；