整数の応用

合同式

和・差・積の余り

和・差・積の余り

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で割った余りを求めよ.

合同式とは何か

合同式とは何か

合同式

2つの整数 $a,b$ を $m$ で割った時の余りが等しいとき, $a$ と $b$ は $m$ を法として合同である,といい

\[a\equiv b\pmod m\]

と表す.

合同式の性質

合同式の性質

合同式については,次のことが成り立つ.

合同式

$a,b,c$ を整数, $m$ を正の整数とするとき,次のことが成り立つ.

  1. $a\equiv a\pmod{m}$
  2. $a\equiv b\pmod{m}$ ならば, $b\equiv a\pmod{m}$
  3. $a\equiv b\pmod{m}$ かつ $b\equiv c\pmod{m}$ ならば, $a\equiv c\pmod{m}$

合同式の性質

$a,b,c,d$ を整数, $m,n$ を正の整数とし,以下 $m$ を法とする. $a\equiv c$ かつ $b\equiv d$ のとき,次のことが成り立つ.

  1. $a+b\equiv c+d$
  2. $a-b\equiv c-d$
  3. $ab\equiv cd$
  4. $a^n\equiv c^n$

倍数の判定

なし

整数の応用的な論点

ピタゴラス数

ピタゴラス数

中国式剰余定理

中国式剰余定理

フェルマーの小定理

フェルマーの小定理