哈代数论读书笔记(五)——同余与剩余

1、Highest common divisor and least common multiple(最大公约数与最小公倍数)

我们已经定义了两个数 $a,b$ 的最大公约数为 $(a,b)$,它有一个计算公式

Theorem 50

$$a=\prod_{p} p^{\alpha}(\alpha \geqslant 0),\quad b=\prod_{p} p^{\beta}(\beta \geqslant 0)$$
那么
$$(a, b)=\prod_{p} p^{\min (\alpha, \beta)}$$

其中 $\min(a,b)$ 表示 $a,b$ 中较小的数,该定理通过算术基本定理很容易证明

$a,b$ 的最小公倍数 ${a, b}$ 定义为能整除这两个数的最小整数

Theorem 51
沿用 Theorem 50 的定义,则有
$${a, b}=\prod_{p} p^{\max (\alpha, \beta)}$$

由上述两个定理,我们可以导出

Theorem 52
$${a, b}=\frac{a b}{(a, b)}$$

如果 $(a,b)=1$,那么我们称 $a,b$ 是 coprime(互质的)

我们称 $a,b,c,\cdots,k$ 是互质的,意思是它们中的任意两个数互质,这个条件比

$$(a, b, c, \ldots, k)=1$$

要强,因为后者只需要这些数中没有大于 $1$ 的公因子即可


2、Congruences and classes of residus(同余与剩余系)

如果 $m$ 是 $(x-a)$ 的因子,那么我们称 $x$ 与 $a$ 模 $m$ 同余,记为

$$x \equiv a(\bmod m)$$

根据定义我们知道

$$x \equiv a(\bmod m) \Leftrightarrow m|(x-a)$$

如果 $x \equiv a(\bmod m)$,那么 $a$ 称为 $x$ 模 $m$ 的 residus(剩余)

特别地,如果 $0\leq a<m$,那么 $a$ 称为 $x$ 模 $m$ 的最小非负剩余

因此,若 $a\equiv b(\bmod m)$,那么 $a,b$ 对于模 $m$ 有相同的剩余

我们用剩余系刻画与模 $m$ 下的一个剩余同余的所有数,每一个剩余系中的数都可以用来表示这个剩余系,因此共有 $m$ 个剩余类

$$0,1,2,\cdots,m-1$$

他们共同组成了模 $m$ 下的 complete system(完全剩余系)

同余符号也可以用于非整数的情况,我们用

$$x\equiv y(\bmod z)$$

表示 $(x-y)$ 是 $z$ 的整数倍,比如

$$\frac{3}{2} \equiv \frac{1}{2}(\bmod 1), \quad-\pi \equiv \pi(\bmod 2 \pi)$$


3、Elementary properties of congruences(同余的性质)

对于模数 $m$,同余显然满足如下性质:

(1)$a \equiv b \rightarrow b \equiv a$

(2)$a \equiv b,b \equiv c \rightarrow a \equiv c$

(3)$a \equiv a^{\prime},b \equiv b^{\prime} \rightarrow a+b \equiv a^{\prime}+b^{\prime}$

如果 $a \equiv a^{\prime}, b \equiv b^{\prime}, \ldots$ 我们有

(4)$k a+l b+\ldots \equiv k a^{\prime}+l b^{\prime}+\ldots$

(5)$a^{2} \equiv a^{\prime 2}, a^{3} \equiv a^{\prime 3},\ldots$

因此,我们导出最终版的结论,如果 $\phi(a, b, \ldots)$ 是整系数多项式

(6)$\phi(a, b, \ldots) \equiv \phi\left(a^{\prime}, b^{\prime}, \ldots\right)$

Theorem 53
如果 $a\equiv b(\bmod m),a\equiv b(\bmod n)$,那么
$$a \equiv b(\bmod {m, n})$$

设 ${m,n}=\prod_{p} p^{c}$,那么对于每一个 $p^c$,有 $p^c|m$ 或 $p^c|n$,因此 $p^c|(a-b)$

由于所有的 $p$ 都是互质的,所以 ${m,n}|(a-b)$,即

$$a \equiv b(\bmod {m, n})$$

该定理可以推广到非整数同余的情况


4、Linear congruences(线性同余)

刚才我们列出的 $6$ 个性质有点类似于线性代数中的式子,但是随后我们发现把它反过来

$$k a \equiv k a^{\prime} \rightarrow a \equiv a^{\prime}$$

不一定成立,比如

$$2\cdot 2\equiv 2\cdot 4(\bmod 4)$$

但是

$$2\not\equiv 4(\bmod 4)$$

接下来,我们考虑这个反过来的式子在什么情况下是成立的

Theorem 54
如果 $(k,m)=d$,那么
$$k a \equiv k a^{\prime}(\bmod m) \rightarrow a \equiv a^{\prime}\left(\bmod \frac{m}{d}\right)$$
逆命题同样成立

我们设

$$k=k_{1} d, \quad m=m_{1} d, \quad\left(k_{1}, m_{1}\right)=1$$

那么

$$\frac{k (a-a^{\prime})}{m}=\frac{k_{1}\left(a-a^{\prime}\right)}{m_{1}}$$

由于 $(k_{1},m_{1})=1$,因此 $m_{1}|(a-a^{\prime})$,即

$$a\equiv a^{\prime}(\bmod \frac{m}{d})$$

证明了这个定理,我们的问题也就随之解决了

Theorem 55
如果 $(k,m)=1$,那么
$$k a \equiv k a^{\prime} \rightarrow a \equiv a^{\prime}(\bmod m)$$

Theorem 56
如果 $a_1,a_2,\cdots,a_m$ 是模 $m$ 下的完全剩余系,且 $(k,m)=1$,那么 $ka_1,ka_2,\cdots,ka_m$ 也是模 $m$ 下的完全剩余系

根据 Theorem 55

$$ka_i\equiv ka_j(\bmod m)\rightarrow a_i\equiv a_j(\bmod m)$$

这个式子成立当且仅当 $i=j$,证毕

更一般地,如果 $(k,m)=1$,那么

$$k a_{r}+l(r=1,2,3, \ldots, m)$$

也是模 $m$ 下的完全剩余系

Theorem 57
如果 $(k,m)=d$,那么同余方程
$$kx\equiv l(\bmod m)$$
有解当且仅当 $d|l$,且方程解数为 $d$

这个同余方程等价于

$$kx-my=l$$

Theorem 25,方程有解条件为 $d|l$

很多初学者可能无法理解,定理中描述解数为 $d$ 是什么意思,明明方程有无穷多的解啊

这里,我们把属于同一剩余系的解看作是相同的

当 $d=1$ 时,很显然这是 Theroem 56 的推论,方程左边的 $kx$ 构成了模 $m$ 下的完全剩余系,方程自然仅有 $1$ 个解

当 $d>1$ 时,设

$$m=d m^{\prime}, \quad k=d k^{\prime}, \quad l=d l^{\prime}$$

那么原同余方程等价于

$$k^{\prime} x \equiv l^{\prime}\left(\bmod m^{\prime}\right)$$

由于 $\left(k^{\prime}, m^{\prime}\right)=1$,方程仅有 $1$ 解,设

$$x \equiv t\left(\bmod m^{\prime}\right)$$

是方程的解,那么

$$x=t+m^{\prime}y$$

接下来回到模 $m$ 下,考察 $t+m^{\prime}y$ 的取值个数,由于

$$t+y m^{\prime} \equiv t+z m^{\prime}(\bmod m) \Leftrightarrow m\left|m^{\prime}(y-z) \Leftrightarrow d\right|(y-z)$$

因此方程有 $d$ 个解,分别为

$$t, \quad t+m^{\prime}, \quad t+2 m^{\prime}, \ldots, \quad t+(d-1) m^{\prime}$$

这里博主惊奇的发现我这近 $600$ 大洋的书竟然出现了印刷错误(口吐芬芳中),有图为证:


5、Euler’s function $\phi(m)$(欧拉函数)

我们定义 $\phi(m)$ 表示区间 $[1,m]$ 中与 $m$ 互质的数的个数

如果 $(a,m)=1$,那么剩余类 $x\equiv a(\bmod m)$ 中的所有数都与 $m$ 互质,这 $\phi(m)$ 个剩余类组成了 complete set of residues prime to m(简化剩余系)

Theorem 58
如果 $a_1,a_2,\ldots,a_{\phi(m)}$ 是简化剩余系且 $(k,m)=1$,那么
$$ka_1,ka_2,\ldots,ka_{\phi(m)}$$
也是简化剩余系

由于 $(ka_i,m)=1$,那么沿用之前的方法,很容易证明该定理

Theorem 59
设 $(m,m^{\prime})=1$,$a$ 取遍模 $m$ 的完全剩余系中的值,$a’$取遍模 $m’$ 的完全剩余系中的值,那么 $a’m+am’$ 取遍了模 $mm’$ 的完全剩余系中的值

$a’m+am’$ 共有 $mm’$ 个取值,假设

$$a_{1}^{\prime} m+a_{1} m^{\prime} \equiv a_{2}^{\prime} m+a_{2} m^{\prime}\left(\bmod m m^{\prime}\right)$$

$$a_{1} m^{\prime} \equiv a_{2} m^{\prime}(\bmod m)$$

由于 $(m,m’)=1$

$$a_1\equiv a_2,\quad a_1’\equiv a_2’$$

因此这 $mm’$ 个取值两两不同余,它们构成了完全剩余系 $(\bmod mm’)$

如果函数 $f(x)$ 满足对于 $(m,m’)=1$,都有

$$f(mm’)=f(m)f(m’)$$

那么我们称 $f(x)$ 是 multiplicative function(积性函数)

Theorem 60
$$\phi(n) 是积性函数$$

设 $(m,m’)=1$,根据 Theorem 59,当 $a$ 取遍模 $m$ 的完全剩余系中的值,$a’$取遍模 $m’$ 的完全剩余系中的值,那么 $a’m+am’$ 取遍了模 $mm’$ 的完全剩余系中的值,且

$$\begin{aligned}\left(a^{\prime} m+a m^{\prime}, m m^{\prime}\right)=1 & \Leftrightarrow\left(a^{\prime} m+a m^{\prime}, m\right)=1 且\left(a^{\prime} m+a m^{\prime}, m^{\prime}\right)=1 \ & \Leftrightarrow\left(a m^{\prime}, m\right)=1 且\left(a^{\prime} m, m^{\prime}\right)=1 \ & \Leftrightarrow(a, m)=1 且\left(a^{\prime}, m^{\prime}\right)=1 \end{aligned}$$

满足 $(a,m)=1且(a’,m’)=1$ 的数对 $(a,a’)$ 共有 $\phi(m)\phi(m’)$ 个

满足 $\left(a^{\prime} m+a m^{\prime}, m m^{\prime}\right)=1$ 的数对 $(a,a’)$ 共有 $\phi(mm’)$ 个,因此

$$\phi(mm’)=\phi(m)\phi(m’)$$

事实上,在刚才的证明过程中,我们本质上证明了下面的定理

Theorem 61
设 $(m,m^{\prime})=1$,$a$ 取遍模 $m$ 的简化剩余系中的值,$a’$取遍模 $m’$ 的简化剩余系中的值,那么 $a’m+am’$ 取遍了模 $mm’$ 的简化剩余系中的值

根据 Theorem 60,如果我们求出了素数的幂的欧拉函数值,那么我们就能求出任意整数的欧拉函数值

对于素数 $p$,小于 $p^c$ 的整数有 $p^c-1$ 个,与 $p^c$ 不互质的数必须含有因子 $p$,因此与 $p^c$ 不互质的数共有 $p^{c-1}-1$ 个,故

$$\phi\left(p^{c}\right)=p^{c}-1-\left(p^{c-1}-1\right)=p^{c}\left(1-\frac{1}{p}\right)$$

更一般地,有如下定理

Theorem 62
若 $m=\Pi_p p^{c}$,那么
$$\phi(m)=m \prod_{p}\left(1-\frac{1}{p}\right)$$

除此之外,我们还能得到一个非常重要的定理

Theorem 63
$$\sum_{d | m} \phi(d)=m$$

设 $m=\Pi_p p^{c}$,那么

$$\begin{aligned} \Phi(m) &=\sum_{d | m} \phi(d)=\sum_{c^{\prime}=0}^{c} \prod_{p} \phi\left(p^{c^{\prime}}\right) \ &=\prod_{p}\left{1+\phi(p)+\phi\left(p^{2}\right)+\cdots+\phi\left(p^{c}\right)\right} \end{aligned}$$

由于

$$1+\phi(p)+\cdots+\phi\left(p^{c}\right)=1+(p-1)+p(p-1)+\cdots +p^{c-1}(p-1)=p^{c}$$

因此

$$\Phi(m)=\prod_{p} p^{c}=m$$


6、Trigonometrical sum(三角和)

在数论中,有三类非常重要的三角和,它们有着类似于积性函数的优美的性质,其证明中用到了 Theorem 59Theorem 61

我们记

$$e(\tau)=e^{2 \pi i \tau},\quad(\tau\in Q)$$

注:$e^{\zeta}=1+\zeta+\frac{\zeta^{2}}{2!}\cdots$,$\zeta$ 是复数

显然,如果 $m \equiv m^{\prime}(\bmod n)$,那么有

$$e\left(\frac{m}{n}\right)=e\left(\frac{m^{\prime}}{n}\right)$$

这个性质使得三角和在数论中有着重要的地位

(1)Gauss’s sum(高斯和)

高斯和在二次剩余领域有非常重要的用处

$$S(m, n)=\sum_{h=0}^{n-1} e^{2 \pi i h^{2} m / n}=\sum_{h=0}^{n-1} e\left(\frac{h^{2} m}{n}\right)$$

根据刚才介绍的同余性质,我们可以写为

$$S(m, n)=\sum_{h(n)} e\left(\frac{h^{2} m}{n}\right)$$

其中,$h(n)$ 表示 $h$ 属于模 $n$ 的完全剩余系

Theorem 64
如果 $(n,n’)=1$,那么
$$S\left(m, n n^{\prime}\right)=S\left(m n^{\prime}, n\right) S\left(m n, n^{\prime}\right)$$

设 $h,h’$ 分别取遍模 $n,n’$ 完全剩余系中的值,那么根据 Theorem 59

$$H=h n^{\prime}+h^{\prime} n$$

取遍模 $nn’$ 完全剩余系中的值,另外有

$$m H^{2}=m\left(h n^{\prime}+h^{\prime} n\right)^{2} \equiv m h^{2} n^{2}+m h^{2} n^{2}\left(\bmod n n^{\prime}\right)$$

因此

$$\begin{aligned} S\left(m n^{\prime}, n\right) S\left(m n, n^{\prime}\right) &=\left{\sum_{h(n)} e\left(\frac{h^{2} m n^{\prime}}{n}\right)\right}\left{\sum_{h^{\prime}(n)} e\left(\frac{h^{\prime 2} m n}{n^{\prime}}\right)\right} \ &=\sum_{h(n), h^{\prime}(n)} e\left(\frac{h^{2} m n^{\prime}}{n}+\frac{h^{\prime 2} m n}{n^{\prime}}\right) \ &=\sum_{h(n), h^{\prime}(n)} e\left(\frac{m\left(h^{2} n^{\prime 2}+h^{\prime 2} n^{2}\right)}{n n^{\prime}}\right) \ &=\sum_{H(nn’)} e\left(\frac{m H^{2}}{n n^{\prime}}\right)=S\left(m, n n^{\prime}\right) \end{aligned}$$

(2)Ramanujan’s sum(拉马努金和)

定义拉马努金和为

$$c_{q}(m)=\sum_{h^{*}(q)} e\left(\frac{h m}{q}\right)$$

其中 $h^{*}(q)$ 表示模 $q$ 的简化剩余系,拉马努金和还有另外一种形式,我们需要先了解一点其它的东西

我们称 $\rho$ 为 primitive q-th root of unity(q次单位原根) 如果 $\rho^{q}=1$ 且不存在比 $q$ 小的整数 $r$ 满足 $\rho^{r}=1$

假设 $\rho^{q}=1$,$r$ 是最小的满足 $\rho^{r}=1$ 的正整数,我们设 $q=kr+s$,其中 $0\leq s<r$,那么

$$\rho^{s}=\rho^{q-k r}=1$$

因此 $s=0\rightarrow r|q$,所有有下述定理

Theorem 65
如果 $q$ 次单位根是 $r$ 次单位原根,那么 $r$ 必为 $q$ 的因子

Theorem 66
所有的 $q$ 次单位根是如下的数:
$$e\left(\frac{h}{q}\right) \quad(h=0,1, \ldots, q-1)$$
该单位根是单位原根的充要条件是 $(h,q)=1$

现在我们写出拉马努金和的另一种形式:

$$c_{q}(m)=\sum_{\rho\in{q次单位原根} } \rho^{m}$$

Theorem 67
如果 $(q,q’)=1$,那么
$$c_{q q^{\prime}}(m)=c_{q}(m) c_{q^{\prime}}(m)$$

根据 Theorem 61

$$\begin{aligned} c_{q}(m) c_{q^{\prime}}(m) &=\sum_{h^{}(q), h^{\prime *}(q)} e\left{m\left(\frac{h}{q}+\frac{h^{\prime}}{q^{\prime}}\right)\right} \ &=\sum_{h^{}(q), h^{\prime *}(q)} e\left{\frac{m\left(h q^{\prime}+h^{\prime} q\right)}{q q^{\prime}}\right}=c_{q q^{\prime}}(m) \end{aligned}$$

感觉我可以把这个积性函数出成 $OI$ 毒瘤题

(3)Kloosterman’s sum

Kloosterman’s 和更为晦涩难懂,

$$S(u, v, n)=\sum_{h^{*}(n)} e\left(\frac{u h+v \overline{h}}{n}\right)$$

其中 $\overline{h}$ 定义为模 $n$ 下的乘法逆元:

$$h\overline{h}\equiv 1(\bmod n)$$

Theorem 57 保证了这样的乘法逆元 $\overline{h}$ 存在且唯一

Theorem 68
如果 $(n,n’)=1$,那么
$$S(u, v, n) S\left(u, v^{\prime}, n^{\prime}\right)=S\left(u, V, n n^{\prime}\right)$$
其中,
$$V=v n^{\prime 2}+v^{\prime} n^{2}$$

$$\begin{aligned} S(u, v, n) S\left(u, v^{\prime}, n^{\prime}\right) &=\sum_{h^{}(q), h^{\prime *}(q)} e\left(\frac{u h+v \overline{h}}{n}+\frac{u h^{\prime}+v^{\prime} \overline{h}^{\prime}}{n^{\prime}}\right) \ &=\sum_{h^{}(q), h^{\prime }(q)} e\left{u\left(\frac{h n+h^{\prime} n}{n n^{\prime}}\right)+\frac{v \overline{h} n^{\prime}+v^{\prime} \overline{h}^{\prime} n}{n n^{\prime}}\right} \ &=\sum_{h^{}(q), h^{\prime *}(q)} e\left(\frac{u H+K}{n n^{\prime}}\right) \end{aligned}$$

这里

$$H=h n^{\prime}+h^{\prime} n, \quad K=v \overline{h} n^{\prime}+v^{\prime} h^{\prime} n$$

根据 Theorem 61,$H$ 取遍模 $nn’$ 简化剩余系中的所有值,那么现在我们只需要证明

$$K \equiv V \overline{H}\left(\bmod n n^{\prime}\right)$$

即可完成

$$S(u, v, n) S\left(u, v^{\prime}, n^{\prime}\right)=\sum_{H} e\left(\frac{u H+V \overline{H}}{n n^{\prime}}\right)=S\left(u, V, n n^{\prime}\right)$$

现在,我们知道

$$\left(h n^{\prime}+h^{\prime} n\right) \overline{H}=H \overline{H} \equiv 1\left(\bmod n n^{\prime}\right)$$

因此

$$h n^{\prime} \overline{H} \equiv 1(\bmod n), \quad n^{\prime} \overline{H} \equiv \overline{h} h n^{\prime} \overline{H} \equiv \overline{h}(\bmod n)$$

所以

$$n^{\prime 2} \overline{H} \equiv n^{\prime} \overline{h}\left(\bmod n n^{\prime}\right)$$

类似的,取另一部分可以得到

$$n^{2} \overline{H} \equiv n^{\prime} \overline{h}^{\prime}\left(\bmod n n^{\prime}\right)$$

这样我们就推导出了

$$V \overline{H}=\left(v n^{\prime 2}+v^{\prime} n^{2}\right) \overline{H} \equiv v n^{\prime} \overline{h}^{\prime}+v^{\prime} n \overline{h}^{\prime} \equiv K\left(\bmod n n^{\prime}\right)$$

定理随之证毕


7、General principle(定理的推广)

我们回到 Theorem 65,如果我们用另一种方式描述定理,可能会省去大量的重复工作

我们用 $P(a)$ 表示关于非负整数 $a$ 的一条性质

Theorem 69
如果 $P(a),P(b)$ 能推导出 $P(a+b),P(a-b)(a\geq b)$,且 $r$ 是满足 $P(r)$ 为真的最小正整数,那么
(1)$P(kr)$ 为真,其中 $k$ 是任意非负整数
(2)任何满足 $P(q)$ 为真的 $q$ 都是 $r$ 的倍数

(1)是非常显然的

(2)注意到 $0<r\leq q$,设

$$q=k r+s, \quad s=q-k r$$

其中 $k\geq 1,0\leq s<r$,由于 $P(r)\rightarrow P(kr)$

$$P(q),P(k r) \rightarrow P(s)$$

根据 $r$ 的定义,$s$ 只能等于 $0$,证毕

取 $P(a):\rho^{a}=1$ 就得到了 Theorem 65 的情况

此条目发表在数学, 数论分类目录。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注