整数の和・差・積を割ったときの余りの関係についてとその証明

整数の和・差・積を割ったときの余りには、ある関係が成り立ちます。
その関係と証明についてまとめます。

前提として、m,kを正の整数とし、2つの整数a,bをmで割った余りをそれぞれr,r'とします。

割り算の関係式から

$a = mq + r$
$b = mq' + r'$

(q,q',r,r'は整数,$0 \leqq r \lt m,0 \leqq r' \lt m$)

とおきます。

a + bをmで割った余りは、r + r'をmで割った余りに等しい

前提式でa + bを表すと

$1.a + b = (mq + r) + (mq' + r ') = m(q + q') + r + r'$

a - bをmで割った余りは、r - r'をmで割った余りに等しい

前提式でa - bを表すと

$2.a - b = (mq + r) - (mq' + r ') = m(q - q') + r - r'$

abをmで割った余りは、rr'をmで割った余りに等しい

前提式でabを表すと

$3.ab = (mq + r)(mq' + r ') = m^2qq' + mqr' + rmq' + rr'$ $= m(mqq' + qr' + q'r) + rr'$

$a^k$をmで割った余りは、$r^k$をmで割った余りに等しい

3の式でb = aとすると

$4.a^2 = (mq + r)^2 = m(mq^2 + 2qr) + r^2$

累乗の数が大きくなるとすると、

$a^k = m × (m,q,rで表される式) + r^k$
になる。

1~4の最終式のm × (整数)をmで割ると余りは0なので、

$a + b,a - b,ab,a^k$をそれぞれmで割った余りは、
$r + r',r - r',rr',r^k$をmで割った余りに等しくなります。

初版:2020/6/28