用高斯/同余数学习数论

定义和基本定理

定义 1.1:

设 $n\in \mathbb {N}$ 且 $a,b\in \mathbb {Z}$. $a$ 和 $b$ 称为 **模 $n$ 同余**，当且仅当 $n|(b-a)$. 在这种情况下，我们写

$a\equiv b\mod n$.

定理 1.2:

设 $n\in \mathbb {N}$ 且 $a\in \mathbb {Z}$. 那么模 $n$ 与 $a$ 同余的数恰好是

$a+m\cdot n,m\in \mathbb {Z}$.

证明:

首先，我们注意到对于每个 $m\in \mathbb {Z}$，都有$n|(a+m\cdot n-a)$。然后设 $n|(b-a)$，即 $b-a=m\cdot n$ 对于某个 $m\in \mathbb {Z}$。然后 $b=a+m\cdot n$。$\Box$

推论 1.3:

关系 $a\equiv b\mod n$ 是一个等价关系。

证明 1:

我们根据定理 1.2 证明这个推论。

自反性：设 $m=0$，我们注意到 $a\equiv a\mod n$。

对称性：设 $a\equiv b\mod n$，即 $b=a+mn$。然后 $a=b+(-m)n$，其中 $-m\in \mathbb {Z}$。

传递性：设 $a\equiv b\mod n$ 且 $b\equiv c\mod n$，即 $b=a+mn$ 且 $c=b+ln$。然后 $c=a+(m+l)n$。$\Box$

证明 2:

我们直接证明这个推论。

自反性：$n|(a-a)$。

对称性：$a\equiv b\mod n\Leftrightarrow n|(b-a)\Leftrightarrow n|(a-b)\Leftrightarrow b\equiv a\mod n$.

传递性：$n|(b-a)$ 且 $n|(c-b)$ 意味着 $b-a=sn$，$c-b=tn$ 对于某些 $s,t\in \mathbb {Z}$。因此，$c-a=c-b+b-a=(s+t)n$.$\Box$

定义 1.4:

令 $a\in \mathbb {Z}$，$n\in \mathbb {N}$。则 $a$ 关于上一定理中等价关系的等价类被称为 **同余类** 或 **模 $n$ 的 $a$ 的剩余类**。

定理 1.5 （欧几里得；带余除法）:

令 $a\in \mathbb {Z}$，$n\in \mathbb {N}$。则存在 $s\in \mathbb {Z}$ 和 $r\in \mathbb {N}$ 使得 $r<n$ 并且

$a=sn+r$.

证明:

考虑集合

$S:=\mathbb {N} _{0}\cap \{a+tn|t\in \mathbb {Z} \}$.

由于这个集合根据定义包含在 $\mathbb {N}$ 中，因此它有一个最小元素。我们将此元素称为 $r$。根据定义，我们得到 $t\in \mathbb {Z}$ 的存在性，使得

$a=(-t)n+r$.

我们定义 $s=-t$。假设 $r>n-1$。那么 $r-n\in S$，这与 $r$ 的最小性相矛盾。$\Box$

我们在此注意，对于那些满足上述定理的环 $R$（使用 $R$ 代替 $\mathbb {Z}$ 和 $\mathbb {N}$，以及一些其他的修改，参见维基百科文章），被称为**欧几里得环**。

定理 1.6:

存在恰好 $n$ 个不同的模 $n$ 同余类，其中 $n\in \mathbb {N}$。

证明 1:

我们用带余除法证明该定理。

我们声称 $0,\ldots ,n-1$ 定义了成对不同的同余类。事实上，假设这两个元素定义了相同的同余类，分别称为 $k$ 和 $j$。那么 $n|(j-k)$，因此特别地 $j-k=0$ 或 $j-k\geq n$。后者是一个矛盾，因为我们可以让 $j$ 尽可能大，并将 $k$ 尽可能小。

现在让 $a\in \mathbb {Z}$。根据带余除法，我们得到 $a=sn+r,s\in \mathbb {Z} ,0\leq r\leq n-1$。然后 $a\equiv r\mod n$，其中 $r$ 在范围内 $0,\ldots ,n-1$。

总之，我们得到每个元素 $0,\ldots ,n-1$ 代表了一个不同的同余类，而且每个其他数字都包含在由这些元素表示的同余类中。由于它们有 $n$ 个，因此定理成立。$\Box$

证明 2:

我们根据推论 1.7 证明该定理（这并非无稽之谈，因为我们给出了两个证明该推论的方法，它们没有基于此引理）。

首先，我们注意到 $0,\ldots ,n-1$ 定义了成对不同的同余类，因为如果 $b\in \{0,\ldots ,n-1\}$，根据推论 1.7，在 $0,\ldots ,n-1$ 中恰好存在一个数字与 $b$ 同余（$b$ 本身）。

然后我们注意到，每个同余类至少由一个 $b\in \mathbb {Z}$ 表示，而根据推论 1.7，它又与其中一个元素 $0,\ldots ,n-1$ 同余。因此，每个同余类都由 $\{0,\ldots ,n-1\}$ 中的一个元素表示。由于这些正好是 $n$ 个不同的元素，因此定理得证。

推论 1.7:

令 $n\in \mathbb {N}$，$a\in \mathbb {Z}$，并令 $n$ 个连续整数 $a,a+1,\ldots ,a+n-1$ 为已知。如果 $b\in \mathbb {Z}$ 是另一个整数，那么，在这 $a,a+1,\ldots ,a+n-1$ 个整数中，只有一个与 $b$ 模 $n$ 同余。

证明 1:

我们利用定理 1.2 来证明这个推论。

Indeed, by theorem 1.2 the integers congruent to $b$ modulo $n$ are given exactly by $b+m\cdot n,m\in \mathbb {Z}$. Assume none of those integers were contained within $\{a,a+1,\ldots ,a+n-1\}$. Define $m_{0}$ to be the largest integer such that $b+m_{0}n<a$ and $m_{1}$ to be the smallest integer such that $a+n-1<m_{1}$. By assumption $m_{1}=m_{0}+1$, since otherwise $m'=m_{0}+1$ would be larger than the largest integer $m_{0}$ such that $b+m_{0}n<a$ and smaller than the smallest integer $m_{1}$ such that $a+n-1<m_{1}$ and hence $a\leq b+m'n\leq a+n-1$ contrary to our assumption. But the difference between $b+m_{0}n$ and $b+m_{1}n=b+(m_{0}+1)n$ is exactly $n$, and in particular there are $n-1$ numbers enclosed between the two. This contradicts the assumption that the numbers $\{a,a+1,\ldots ,a+n-1\}$ are enclosed within the two; those are $n$ different numbers.

假设集合$\{a,a+1,\ldots ,a+n-1\}$ 中有两个整数对模$n$ 同余于$b$。将它们分别记为$a+j$ 和$a+l$。那么根据定理 1.2，$a+j=b+sn$，$a+l=b+tn$，其中$s,t\in \mathbb {Z}$。因此，$j-l=(s-t)n$。特别地，$l$ 和$j$ 之差要么为零，要么大于或等于$n$，这与集合$\{a,a+1,\ldots ,a+n-1\}$ 中任意两个数字之差小于或等于$n-1$（因为我们可以通过将较小的元素移动到$a$，并将较大的元素移动到$a+n-1$ 来最大化这个差) 相矛盾。$\Box$

证明 2:

我们使用定理 1.2 和分数来证明推论。

如果 ${\frac {a-b}{n}}$ 是一个整数，那么 $a\equiv b\mod n$。 否则， ${\frac {a-b}{n}}$ 是一个分数。 令 $k$ 是下一个更大的整数。 那么

$a=b+{\frac {a-b}{n}}\cdot n<b+kn<b+{\frac {a-b+n}{n}}\cdot n=a+n$

因此 $b+k\cdot n$ 包含在 $\{a,a+1,\ldots ,a+n-1\}$ 中。 此外，对于所有 $l\in \{0,\ldots ,n-1\}$

$k-1<{\frac {a-b}{n}}\leq {\frac {a+l-b}{n}}<{\frac {a+n-b}{n}}<k+1$,

只有其中的一个分数 ${\frac {a+l-b}{n}}$ 可以是整数，这等价于 $n|(a+l-b)$。$\Box$

证明 3:

我们从同余类的概念和引理 1.6 证明这个推论。

事实上，与引理 1.6 完全类似，我们证明了$a,\ldots ,a+n-1$表示成对不同的同余类。由于它们恰好有$n$个，元素$a,\ldots ,a+n-1$实际上代表了所有同余类。由于任何等价关系的等价类构成一个划分，我们得出结论，每个$b\in \mathbb {Z}$都与$a,\ldots ,a+n-1$中的一个同余。$\Box$

剩余

定义 1.7:

令$a\in \mathbb {Z}$且$n\in \mathbb {N}$。 $b\in \mathbb {Z}$被称为$a$模$n$的剩余当且仅当$a\equiv b\mod n$。

从定理 1.2 可以直接得出，$a\in \mathbb {Z}$模$n$的剩余恰好是以下这些数

$a+mn,m\in \mathbb {Z}$.

引理 1.8

令$a\in \mathbb {Z}$且$n\in \mathbb {N}$。 那么$a$在$\{-(n-1),\ldots ,-1,0\}$内恰好有一个剩余，在$\{0,1,\ldots ,n-1\}$内也恰好有一个剩余。当且仅当$n|a$时，它们重合。

证明:

这从推论 1.6 以及 $a=-(n-1)$ 或 $a=0$ 推出，分别。 $\Box$

定义 1.9:

引理 1.8 中的两个余数分别称为负最小余数和正最小余数。

定理 1.10:

设 $a\in \mathbb {Z}$，$n\in \mathbb {N}$，$l\in \{-(n-1),\ldots ,0\}$ 是负最小余数，而 $j\in \{0,\ldots ,n-1\}$ 是正最小余数。那么会出现以下四种情况之一：

1. $|l|=|j|=n/2$
2. $|l|>n/2>|j|$
3. $|l|<n/2<|j|$
4. $|l|=|j|=0$

证明:

我们有 $n|(a-j)$，因此 $n|(a+n-j)$，即 $n|(a-(j-n))$。我们将四种情况分开：

1. $|j|=0$。由于 $j=|j|$，零同时是正最小余数和负最小余数。

定理与定义 1.11:

令 $a\in \mathbb {Z}$ 且 $n\in \mathbb {N}$。在范围 ${\displaystyle }$ 内恰好存在一个余数

整除性判定法

定理 1.?:

令 $a\in \mathbb {Z}$ 由十进制展开式 $a_{n}\cdots a_{1}a_{0}$ 给出，即

$a=\sum _{j=0}^{n}a_{j}10^{j}$.

则 $a$ 能被 3 或 9 整除当且仅当 $\sum _{j=0}^{n}a_{j}$ 能被整除。

证明:

由于 $10\equiv 1\mod 9$（因此 $10\equiv 1\mod 3$），我们有

$\sum _{j=0}^{n}a_{j}10^{j}\equiv \sum _{j=0}^{n}a_{j}\mod k$，$k\in \{3,9\}$。$\Box$

习题

• 习题 1.?.1: