割り算の余りの性質
合同
≡は合同を表す記号
a ≡ b (mod m)は、aをmで割った余りとbをmで割った余りが等しいことを表す
(mod m)
a ≡ b, c ≡ d
のとき、以下成り立つ
a+b ≡ c+d
a*b ≡ c*d
e.g. 値1357で考える
(mod 13)
1 ≡ 1, 10 ≡ 10
(1*10) ≡ (1*10)
10 ≡ 10
10 ≡ 10, 3 ≡ 3
10+3 ≡ 10+3
13 ≡ 13 ≡ 0
13 ≡ 0, 10 ≡ 10
130 ≡ 0
130 ≡ 0, 5 ≡ 5
135 ≡ 5
135 ≡ 5, 10 ≡ 10
1350 ≡ 50 ≡ 11
1350 ≡ 50, 7 ≡ 7
1357 ≡ 57 ≡ 5
DPで配る
(mod 13)
1 ≡ 1
13 ≡ (1*10+3 % 13) ≡ 0
135 ≡ (0*10+5 % 13) ≡ 5
1357 ≡ (5*10+7 % 13) ≡ 5