线性同余方程组 $m_i$不互素

hbghlyj

关于$m_i$不互素的2个线性方程的组, 有以下定理, 在原文中没有给出证明:

Theorem. Consider the system
$$\eqalign{ x & = a_1 \mod{m_1} \cr x & = a_2 \mod{m_2}}.$$
(a) If $(m_1, m_2) \nmid a_1 - a_2$ , there are no solutions.
(b) If $(m_1, m_2) \mid a_1 - a_2$ , there is a unique solution mod $[m_1, m_2]$.
Note that if $(m_1, m_2) = 1$ , case (b) automatically holds, and $[m_1, m_2] = m_1 m_2$ — i.e. I get the Chinese Remainder Theorem for $n = 2$

(a)
方程组可以写成$m_1|(x-a_1),m_2|(x-a_2)$
且$(m_1, m_2)$整除$m_1$与$m_2$
所以$(m_1, m_2)$整除$(x-a_1)$与$(x-a_2)$, 所以整除$a_1-a_2$.
(b)
使用原文中的iterative method解这个不定方程:
将$x=a_1+m_1t$代入第二式,
$$m_1t = a_2-a_1 \mod{m_2}$$
除以$(m_1, m_2)$,
$$\frac{m_1}{(m_1,m_2)}t = \frac{a_2-a_1}{(m_1,m_2)} \mod\frac{m_2}{(m_1,m_2)}$$
因为$\frac{m_1}{(m_1,m_2)}$与模数$\frac{m_2}{(m_1,m_2)}$互素, 所以存在modular inverse $s_1$, 乘以$s_1$得到,
$$t = \frac{a_2-a_1}{(m_1,m_2)}s_1 \mod\frac{m_2}{(m_1,m_2)}$$
乘以$m_1$,
$$m_1t = \frac{a_2-a_1}{(m_1,m_2)}s_1m_1 \mod\frac{m_1m_2}{(m_1,m_2)}$$
用$\frac{m_1m_2}{(m_1,m_2)}=[m_1,m_2]$,
$$m_1t = \frac{a_2-a_1}{(m_1,m_2)}s_1m_1 \mod[m_1,m_2]$$
加上$a_1$得到原方程组的解,
$$x=a_1+ \frac{a_2-a_1}{(m_1,m_2)}s_1m_1 \mod[m_1,m_2]$$
代回去验证确实满足原方程组, 所以原方程组有唯一解. [或者可以说, 每步都是等价变换, 可以逆推回去, 所以原方程组有唯一解]

hbghlyj

问一个TeX的事情:
\max 和 \mod 对于 \over 的影响不同?
比如 \max{m_2\over(m_1,m_2)} 给出 $$\max{m_2\over(m_1,m_2)}$$
而 \mod{m_2\over(m_1,m_2)} 却给出 $$\mod{m_2\over(m_1,m_2)}$$