和・差・積の余り

和・差・積の余り

5+6を4で割った余りは, $5+6=11$ であるから, $11=4\cdot2+3$ より3である.

これは,5を4で割った余りの1と,6を4で割った余りの2を加えた3と等しい.

すなわち,「足してから割った余り」と「割ってから足した余り」が等しくなっている. 一般的に次のことが言える.

和・差・積の余り

2つの整数 $a,b$ を $m$ で割った時の余りを,それぞれ $r,r'$ とすると,次のことが成り立つ.

  1. $a+b$ を $m$ で割った余りは, $r+r'$ を $m$ で割った余りと等しい.
  2. $a−b$ を $m$ で割った余りは, $r−r'$ を $m$ で割った余りと等しい.
  3. $ab$ を $m$ で割った余りは, $rr'$ を $m$ で割った余りと等しい.

【証明】

和・差・積の余り

  1. $5^{100}$ を4で割った余りを求めよ.
  2. $2^{100}$ を7で割った余りを求めよ.