注：本节内容为《具体数学》(原书第二版) 第四章 数论 4.6 mod: 同余关系 的旁注。

P103 $a \equiv 0 \Rightarrow ak \equiv 0$

证明：

$$
a \equiv 0 \pmod m \Leftrightarrow a-0 = mp, p\in \mathbb Z
$$

故

$$
ak - 0 = m(pk)
$$

等价于

$$
ak \equiv 0 \pmod m
$$

P103 $a + b \equiv c+ d \pmod m$

$$
a\equiv b, c\equiv d \Rightarrow a + c \equiv b + d
$$

证明：

$$
a \equiv b \pmod m \Leftrightarrow a-b = mp, p\in \mathbb Z
$$

$$
c \equiv d \pmod m \Leftrightarrow c-d = mq, q\in \mathbb Z
$$

故有

$$
(a+c) - (b+d) = m(p+q) \Leftrightarrow a+c=b+d\pmod m
$$

减法可由相似方法证明。

P103 $ac \equiv bd \pmod m$

$$
a\equiv b, c\equiv d \Rightarrow ac \equiv bd
$$

证明：

$$
a\equiv b \Rightarrow (a-b) \equiv 0
$$

$$
c\equiv d \Rightarrow (c-d) \equiv 0
$$

根据刚证的结论，

$$
(a-b)c \equiv 0, (c-d)b \equiv 0
$$

$$
(a-b)c+(c-d)b = ac-bd \equiv 0
$$

$$
ac = (ac-bd)+bd \equiv bd
$$

即

$$
ac \equiv bd
$$

P104 $ad \equiv bd \Leftrightarrow a\equiv b \pmod m, d \perp m$

根据裴蜀定理以及扩展欧几里得算法，我们总能找到 $d'$，使其满足：

$$
d'd + m'm = \gcd(d,m) = 1
$$

可以发现，其满足 $d'd \equiv 1 \pmod m$，顺带一提，这便是 $d$ 对于 $m$ 的乘法逆元。

有了这个 $d'$，我们就可以开始证明。

充分性：

$$
ad \equiv bd, d' \equiv d' \Rightarrow add' \equiv bdd'
$$

$$
dd' \equiv 1, a \equiv a \Rightarrow add' \equiv a
$$

同理

$$
bdd' \equiv b
$$

所以

$$
a \equiv b
$$

必要性：

$$
a\equiv b, d\equiv d \Rightarrow ad \equiv bd
$$

P104 $ad \equiv bd \pmod {md} \Leftrightarrow a \equiv b \pmod m, d \neq 0$

证明：

$$
a\equiv b \pmod m \Leftrightarrow (a\bmod m) d = (b\bmod m) d
$$

令

$$
a \pmod m = r
$$

有

$$
a = tm + r
$$

$$
ad = tdm + rd
$$

$$
ad \pmod {dm} = rd = (a \bmod m) d
$$

故

$$
(a\bmod m) d = (b\bmod m) d \Leftrightarrow ad \bmod md = bd \bmod md
$$

$$
a\equiv b \pmod m \Leftrightarrow ad \equiv bd \pmod {md}
$$

P104 $ad \equiv bd \pmod m \Leftrightarrow a\equiv b \pmod {\frac {m}{\gcd(d,m)}}$

方法一：

这里只证明充分性，必要性可以通过前面证得的定理 $(4.38)$ 推得。

根据裴蜀定理以及扩展欧几里得算法，我们总能找到 $d'$，使其满足：

$$
d'd + m'm = \gcd(d,m) = 1
$$

所以

$$
dd' \equiv \gcd(d,m) \pmod m
$$

故有

$$
ad'd \equiv a \gcd(d,m) \pmod m
$$

$$
bd'd \equiv b \gcd(d,m) \pmod m
$$

又因为

$$
ad \equiv bd, d' \equiv d' \Rightarrow add' \equiv bdd'
$$

可得

$$
a \gcd(d,m) \equiv b\gcd(d,m) \pmod m
$$

根据 $(4.38)$ 有

$$
a \equiv b \pmod {\frac m {\gcd(d,m)}}
$$

方法二：

可以通过唯一分解式比较 $d_p, m_p$ 证明：

$$
\gcd(\frac d {\gcd(d,m)}, \frac m {\gcd(d,m)}) = 1
$$

随后便可通过 $(4.38)$ 获得这个充要关系。

P104 $a\equiv b \pmod {md} \Rightarrow a \equiv b \pmod m$

证明：

$$
a \equiv b \pmod {md} \Leftrightarrow a - b = mdt, t\in \mathbb Z
$$

$$
\Rightarrow a - b = m(dt) \Leftrightarrow a \equiv b \pmod m
$$

P104 $a \equiv b \pmod m, a \equiv b \pmod n \Leftrightarrow a \equiv b \pmod {\operatorname{lcm}(m,n)}$

证明：

$$
a \equiv b \pmod m
$$

$$
a \equiv b \pmod n
$$

等价于 $a - b$ 为 $m,n$ 的公倍数，等价于 $a-b$ 为 $\operatorname{lcm}(m,n)$ 的倍数，等价于

$$
a \equiv b \pmod {\operatorname{lcm}(m,n)}
$$