注：本节内容为《具体数学》(原书第二版) 第四章 数论 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)}
$$
