遅くなりましたが、>>36 で使った mod の定義とその性質の証明を書きます。
[mod の定義]
正の整数 m , 整数 a , b に対して a - b が m の倍数のとき、
a と b は m を法として合同と言い、a ≡ b (mod m ) と書く。
a ≡ b , c ≡ d (mod m) なら、
(i) a + c ≡ b + d (mod m)
(ii) a - c ≡ b - d (mod m)
(iii) a*c ≡ b*d (mod m)
[証明]
(i) (a + c) - (b + d) = (a - b) + (c - d) ≡ 0 (mod m)
(ii) (a - c) - (b - d) = (a - b) - (c - d) ≡ 0 (mod m)
(iii) a*c - b*d = (a - b)*c + b*(c - d) ≡ 0 (mod m)
また、(iii) で c = a , d = b として
a^2 ≡ b^2 (mod m)
同様にして
a^3 ≡ b^3 (mod m)
………………………
以下、帰納的に
a^n ≡ b^n (mod m) (但し n は自然数 ) が成り立つ。■
