用高斯/同餘數學習數論

定義和基本定理

定義 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: