| 合同式の定義より
a[i] ≡ b[i] (mod m) ⇔ 整数 p[i] が存在して a[i] - b[i] = p[i] m
(i = 1, 2, ... n)です。
(1) したがって
納i:1→n] a[i] - 納i:1→n] b[i] = 納i:1→n](a[i] - b[i]) = (納i:1→n] p[i]) m ⇔ 納i:1→n] a[i] ≡ 納i:1→n] b[i] (mod m)
となります。
(2) 一方、
Π[i:1→k] a[i] - Π[i:1→k] b[i] = Π[i:1→k-1] a[i] × (a[k] - b[k]) + ( Π[i:1→k-1] a[i] - Π[i:1→k-1] b[i] ) b[k]
なので、α[k] = Π[i:1→k] a[i] - Π[i:1→k] b[i] と置くと、漸化式
α[1] = a[1] - b[1] = p[1] m α[k] = Π[i:1→k-1] a[i] p[k] m + b[k] α[k-1], k = 2, 3, ..., n
が得られます。よって、α[n] は m の倍数であり
Π[i:1→k] a[i] ≡ Π[i:1→k] b[i] (mod m)
となります。
|