在這一節中我們都假設
f (x) = anxn + ... + a1x + a0, 其中
ai
, 而
m
是一給定的正整數. 我們要談論
f (x)
0(mod m) 這一個 congruence equation.
第一種情形是這樣的: 如果 d 是
an,..., a1, a0 以及 m
的正公因數. 也就是說我們可以將 ai 及 m 寫成
an = an'd,..., a1 = a1'd, a0 = a0'd 以及 m = m'd, 其中這些
ai'
且
m'
. 令
g(x) = an'xn + ... a1'x + a0',
我們來探討
f (x)
0(mod m) 及
g(x)
0(mod m') 這兩個
congruence equation 之間的關係.
若
x c(mod m') 是
g(x)
0(mod m') 的一個解,
則對任意
t
,
x
c + m't(mod m) 為
f (x)
0(mod m) 的解. 另一方面, 若
g(x)
0(mod m') 無解, 則
f (x)
0(mod m) 無解.
對任意
t
以及
r
, 由於
(c + m't)r = cr + rcr - 1m't + ... + rc(m't)r - 1 + (m't)r, 我們可以將
(c + m't)r 寫成
cr + m'
, 其中
. 因此
另一方面, 若
x c(mod m) 為
f (x)
0(mod m) 的一個解,
即
m| ancn + ... + a1c + a0, 則
m'| an'cn + ... + a1'c + a0'.
也就是說
x
c(mod m') 為
g(x)
0(mod m') 的一個解.
因此若
g(x)
0(mod m') 無解, 則
f (x)
0(mod m)
亦無解.
Proposition 4.2.1 告訴我們, 如果
x c(mod m') 是
g(x)
0(mod m') 的一個解, 則對任意
t
,
x
c + m't(mod m) 便會是
f (x)
0(mod m) 的一個解.
不過這裡由於我們要考慮在 modulo m 的情況, 很多解是重複的. 事實上若
t
t'(mod d), 則由 d| t - t', 可得
dm'| m'(t - t'). 也就是說
c + m't
c + m't'(mod m). 因此我們只要考慮
x
c + m't(mod m) 其中
0
t
d - 1, 就可以了.
Proposition 4.2.1 將一個 modulo m 的 congruence equation 化成一個 modulo 比較小的 m' 的 congruence equation. 這樣一來由於在 modulo m' 之下要考慮的數較少, 應該將原來的問題簡化了. 然而若 an,..., a1, a0 和 m 是互質的, 我們仍然可以考慮 modulo 較小的值看看有沒有解. 事實上, 我們有以下之結果.
Lemma 4.2.2 和 Proposition 4.2.1 不同之處在於 Proposition 4.2.1 將原多項式各係數除以公因數後考慮 modulo m' 之解, 而且可利用其解得到原多項式在 modulo m 之解, 而 Lemma 4.2.2 並沒有改變多項式, 且僅知原多項式在 modulo 比較小的 m' 之下無解可推得原多項式在 modulo m 之下無解. 但無從判斷在 modulo m' 之下有解是否可得在 modulo m 之下有解, 而且也無從推得解之形式. 不過若我們多考慮幾個 m 的因數所得的 congruence equations, 確實可以幫我們得知解之情形. 這就是我們要探討的第二種方法.
這一種常用的方法就是先將 m 寫成質因數的分解, 即
m = p1n1 ... prnr, 其中這些 pi 為相異質數. 接著僅要探討對所有
i = 1,..., r,
f (x) 0(mod pini) 之解的情形就可,
因為我們有以下之結果.
現假設
x c(mod m) 為
f (x)
0(mod m) 的一個解,
也就是說 m| f (c), 由於對任意
i
{1,..., r} 皆滿足
pini| m, 知
pini| f (c). 因此知對所有的
i
{1,..., r},
x
c(mod pini) 為
f (x)
0(mod pini) 的解.
反之, 若對所有
i {1,..., r},
x
c(mod pini) 皆為
f (x)
0(mod pini) 的解. 即
pini| f (c). 則由於這些
pini 是兩兩互質的, 利用 Proposition 1.2.7(2) 知
p1n1 ... prnr| f (c), 亦即 m| f (c). 故得證
x
c(mod m) 為
f (x)
0(mod m) 的一個解.
Proposition 4.2.3 告訴我們, 若有一個 pi 使得
f (x) 0(mod pini) 無解, 那麼
f (x)
0(mod m) 就無解.
但是如果對所有的 pi,
f (x)
0(mod pini) 皆有解,
是否表示
f (x)
0(mod m) 有解呢? 答案是肯定的.
這是因為雖然對任意的 pi 解得的解未必相同,
但利用以後會探討的中國剩餘定理可找到一整數同時滿足 modulo
pini 下每個解的形式, 因此可由 Proposition 4.2.3 得知
f (x)
0(mod m) 有解.
關於此部份以後在探討中國剩餘定理時我們會再說明.