整数

贡献者： JierPeter; addis; Giacomo

本文处于草稿阶段。

预备知识　二元关系

　　整数的概念是大家所熟悉的。严格的数学中对于整数的定义过于抽象，主要是为了逻辑基础的严谨性；严格定义依然是建立在我们熟知的整数概念上的，所以在物理学习中没必要深入到整数的定义上，读者只需要按照通常的理解方式来认识整数就可以。我们把整数构成的集合称为整数集（Set of Integers），记为 $Z$ 。

　　整数通常涉及的运算有加法和乘法。加法的逆运算被称为减法，且减法在整数集上是封闭的，即两个整数相减仍为整数；乘法的逆运算被称为除法，除法在整数集上就不封闭，例如 $2 / 3 \notin Z$ ，尽管 $2$ 和 $3$ 都属于 $Z$ 。

　　在中小学中我们学过带余除法，用现代数学语言可以记成如下形式：当被除数为 $a$ ，除数为 $b$ ，余数为 $c$ 的时候，存在一个整数 $k$ ，使得 $a = k b + c$ 。作为练习，用逻辑量词来表达时，这句话可以写为：当被除数为 $a$ ，除数为 $b$ ，余数为 $c$ 的时候， $\exists k \in Z$ , s.t. $a = k b + c$ 。在群论（group theory）、环论（ring theory）和域论（field theory）中，我们会遇到大量基于模运算概念的运算。本文中，我们会使用钟表模型来阐释如何进行模运算。

　　将除数固定为 $b$ ，那么如果两个整数 $a_{1}$ 和 $a_{2}$ 除以 $b$ 所得到的余数相同，我们就称 $a_{1}$ 和 $a_{2}$ 模 $b$ 同余（ $a_{1} \equiv a_{2} \mod b$ ）。这里模的意思类似于 “除以”，同余的意思是 “余数相同”。在这种情况下，我们也把 $a_{1}$ 和 $a_{2}$ 称为彼此的模 $b$ 的同余数（congruence mod $b$ ）。为了简化表达，当默认了 $b$ 的取值以后，我们也可以把 $\mod b$ 省略，简单地称 $a_{1}$ 和 $a_{2}$ 同余（congruent），并记为 $a_{1} \equiv a_{2}$ 。

　　由文章二元关系中对等价关系的讨论可以推知，给定整数 $b$ 以后，模 $b$ 同余的关系是一个整数集上的等价关系。也就是说，我们可以利用 $b$ 把整数集划分为若干个等价类，称作整数集模 $b$ 的同余类（congruence class）。由等式 $a = k b + c$ 可知， $a$ 就在模 $b$ 余 $c$ 的同余类中。在文章二元关系中所讨论的 “两数的差是 3 的倍数” 这一关系，其实就是一个模 3 同余的关系。

1. 钟表和模算数

　　钟表的模型可以帮助你直观地理解模运算，以及初步感受 “集合间的运算” 是什么样的。

　　我们所熟知的加法、减法和乘法运算是在一个无穷集合上讨论的，即整数集。如果把 “等于” 的概念替换为 “模同余” 的概念，我们就可以在有限集合上进行加法、减法和乘法运算。最常见的例子，是钟表上整点的计算，这是一个模 12 同余的运算。

　　模运算的概念是，给定用来作除数的 $b$ 以后，将模 $b$ 同余的整数都看成同一个。在钟表的例子里， $b = 12$ ，那么我们把 $0, 12, 24, 72$ 等都看成同一个元素， $3, 15, 27, 147$ 等也都看成同一个元素。判断整数 $a_{1}$ 和 $a_{2}$ 是否模 12 同余的方法很简单，就是看 $a_{1} - a_{2}$ 是否是 12 的倍数。这样，我们可以把整数轴卷起来，让所有彼此同余的整数都重合起来，此时 12 点就是 0 点，14 点就是 2 点，28 点就是 4 点。为了方便讨论，我们只取 $0, 1, 2, \dots, 11$ 分别作为 12 个同余类的代表，然后进行运算。

　　我们要讨论的是，从两个同余类中随便取一个数字，将它们进行加法，减法或者乘法运算后，结果落入哪一个同余类。在这样的运算规则下，用上一段所规定的代表元来进行讨论的话，我们可以得到以下运算的例子：

\begin{matrix} (1) & \begin{aligned} 1 + 1 \equiv 2, 4 + 8 \equiv 0, 11 + 8 \equiv 7, \\ 3 - 2 \equiv 1, 5 - 7 \equiv 10, \\ 2 \times 3 \equiv 6, 3 \times 4 \equiv 0, 4 \times 7 \equiv 4 . \end{aligned} \end{matrix}

　　模运算有一个美妙的性质。如果 $a_{1}$ 和 $a_{2}$ 同余，那么我们可以将它们的关系表达为 $a_{1} = a_{2} + 12 k$ ，其中 $k$ 是唯一存在的整数。利用这个关系容易证明，对于任意的整数 $a_{3}$ ，我们都有 $a_{1} + a_{3} \equiv a_{2} + a_{3}$ ， $a_{1} - a_{3} \equiv a_{2} - a_{3}$ 以及 $a_{1} \times a_{3} \equiv a_{2} \times a_{3}$ 。这三个式子实际上说明了，在进行同余类的加法、减法和乘法的时候，无论取谁作为代表元素，结果都还是在同一个同余类里。因此我们才可以放心地把同余类的运算看作是任意代表元之间的运算，比如钟表整点的计算。

　　在通常的钟表中，我们把整数轴卷成周长为 12 的钟表。我们也可以把整数轴按其它周长来卷曲。当把整数轴卷曲成周长为 $b$ 的钟表时，在钟表上进行的加减和乘法运算就是数学家们所讨论的模 $b$ 的加减和乘法运算。

　　一般地，我们把一个如上定义的、含 $n$ 个钟点、定义了加法和乘法的结构，记为 $Z_{n}$ 。这是 “环” 的一个例子，参见文章环以及其后的内容。

2. 素数

　　根据小学所学定义，素数（prime numbers）是指那些除了 1 和自身以外没有别的因子的整数。

　　在代数学中，整数集是交换环（commutative ring）的一个特例，而素数是更广义的交换环的素元素（prime element of a commutative ring）的一个特例。根据交换环中素元素的定义，整数中的素数 $p$ 是满足如下需求的整数：如果 $p$ 能整除 $a b$ ，其中 $a$ 和 $b$ 是任意满足条件的整数组合，那么 $p$ 必能整除 $a$ 和 $b$ 中的一个。用逻辑量词来简洁地表达，就是： $\forall a, b \in Z$ ，如果 $p | a b$ ，那么要么 $p | a$ ，要么 $p | b$ 。

致读者：小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。因此，我们请求广大读者热心打赏 ，使网站得以健康发展。如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损，并在接下来的一年里向所有读者继续免费提供优质内容。但遗憾的是只有不到 1% 的读者愿意捐款，他们的付出帮助了 99% 的读者免费获取知识，我们在此表示感谢。