 | 合同式の定義より
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)
となります。
|