数学A 第4章整数の性質 — 整数の応用

合同式

和・差・積の余り

5+6を4で割った余りは， $5+6=11$ であるから， $11=4・2+3$ より3である．

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

すなわち，「足してから割った余り」は，「それぞれの余りを足したもの」をもう一度4で割った余りに等しい．

余りを足しただけでは，そのまま余りになるとは限らない．例えば， $7+6=13$ を4で割った余りは1であるが，7を4で割った余りの3と，6を4で割った余りの2を足すと5となる．この5をもう一度4で割った余りが1となり，一致する．一般的に次のことが言える．

定理1和・差・積の余り

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

$a+b$ を $m$ で割った余りは， $r+r'$ を $m$ で割った余りと等しい．
$a-b$ を $m$ で割った余りは， $r-r'$ を $m$ で割った余りと等しい．
$ab$ を $m$ で割った余りは， $rr'$ を $m$ で割った余りと等しい．
$a^n$ を $m$ で割った余りは， $r^n$ を $m$ で割った余りと等しい（ $n$ は正の整数）．

証明

$a$ を $m$ で割った商を $q$ ， $b$ を $m$ で割った商を $q'$ とすると

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

と表せる．このとき

$a+b=m(q+q')+(r+r') a-b=m(q-q')+(r-r') ab=m(mqq'+qr'+q'r)+rr'$

となる．

いずれも右辺の第1項は $m$ の倍数であるから， $m$ で割った余りには影響しない．よって， $a+b$ を $m$ で割った余りは $r+r'$ を $m$ で割った余りに等しく，差と積についても同様である．

また，4は3を繰り返し使えばよい．

∎

問題1和・差・積の余り

$5¹⁰⁰$ を4で割った余りを求めよ．
$2¹⁰⁰$ を7で割った余りを求めよ．

解答を見る

$5=4・1+1$ であるから，5を4で割った余りは1である．

したがって，和・差・積の余りの4より， $5¹⁰⁰$ を4で割った余りは， $1¹⁰⁰=1$ を4で割った余り，すなわち $1$ である．
$2³=8=7・1+1$ であるから， $2³$ を7で割った余りは1である．

ここで， $100=3・33+1$ であるから

$2¹⁰⁰=(2³)³³・2$

と表せる． 和・差・積の余りの4より， $(2³)³³$ を7で割った余りは $1³³=1$ であり，同じく3より， $2¹⁰⁰$ を7で割った余りは $1・2=2$ を7で割った余り，すなわち $2$ である．

合同式とは何か

定義2合同式

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

$a\equiv b\pmod m$

と表す．

例えば，17も2も，5で割った余りは2であるから， $17\equiv2\pmod5$ である．

この記号を使うと，前の小節の和・差・積の余りは， $a\equiv r$ ， $b\equiv r'$ のとき

$a+b\equiv r+r', a-b\equiv r-r', ab\equiv rr'$

と短く書ける．

また， $a\equiv b\pmod m$ であることは， $a-b$ が $m$ の倍数であることと同じである．

実際， $a=mq+r$ ， $b=mq'+r$ と余りが等しいとすると

$a-b=m(q-q')$

となり， $a-b$ は $m$ の倍数である．逆に $a-b$ が $m$ の倍数ならば，整数 $k$ を用いて $a=b+mk$ と書けるので， $b=mq'+r$ より

$a=m(q'+k)+r$

となり，余りはやはり等しい．

合同式の性質

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

定理3合同式

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

$a\equiv a\pmodm$
$a\equiv b\pmodm$ ならば， $b\equiv a\pmodm$
$a\equiv b\pmodm$ かつ $b\equiv c\pmodm$ ならば， $a\equiv c\pmodm$

証明

いずれも「差が $m$ の倍数であること」に言いかえて示す．

$a-a=0=m・0$ であるから，1が成り立つ．

$a\equiv b\pmodm$ ならば，整数 $k$ を用いて $a-b=mk$ と書けるので， $b-a=m(-k)$ となり，2が成り立つ．

さらに， $b\equiv c\pmodm$ でもあるとき，整数 $l$ を用いて $b-c=ml$ と書けるので

$a-c=(a-b)+(b-c)=m(k+l)$

となり，3が成り立つ．

∎

定理4合同式の性質

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

$a+b\equiv c+d$
$a-b\equiv c-d$
$ab\equiv cd$
$a^n\equiv c^n$

証明

仮定より， $a-c$ と $b-d$ は $m$ の倍数であるから，整数 $k,l$ を用いて $a-c=mk$ ， $b-d=ml$ とおける．このとき

$(a+b)-(c+d)=m(k+l) (a-b)-(c-d)=m(k-l) ab-cd=a(b-d)+d(a-c)=m(al+dk)$

となり，いずれも $m$ の倍数であるから，1〜3が成り立つ．

4は，3を繰り返し使えばよい．

∎

問題2倍数の判定

3けたの自然数 $N$ の各位の数の和が3の倍数ならば， $N$ も3の倍数であることを，合同式を使って示せ．
1234を11で割った余りを， $10\equiv-1\pmod11$ であることを使って求めよ．

解答を見る

$N$ の百の位を $a$ ，十の位を $b$ ，一の位を $c$ とすると， $N=100a+10b+c$ である．

$10\equiv1\pmod3$ であるから， $10²\equiv1\pmod3$ となり

$N\equiv a+b+c\pmod3$

よって， $a+b+c$ が3の倍数ならば， $N$ を3で割った余りも0，すなわち $N$ は3の倍数である．
$10\equiv-1\pmod11$ より， $10²\equiv1$ ， $10³\equiv-1$ であるから

$1234=10³+2・10²+3・10+4 \equiv-1+2-3+4 =2\pmod11$

よって，求める余りは $2$ である．

整数の応用的な論点

ピタゴラス数

定義5ピタゴラス数

$a²+b²=c²$ を満たす自然数の組 $(a,b,c)$ を，ピタゴラス数という．

例えば， $(3,4,5)$ や $(5,12,13)$ はピタゴラス数である．

定理6ピタゴラス数の表し方

$a,b,c$ の最大公約数が1であるピタゴラス数は， $a$ を奇数， $b$ を偶数とすると，互いに素で一方が偶数，他方が奇数であるような自然数 $m>n$ を用いて

$a=m²-n², b=2mn, c=m²+n²$

の形にすべて表せる．実際， $m=2$ ， $n=1$ とすると $(3,4,5)$ が， $m=3$ ， $n=2$ とすると $(5,12,13)$ が得られる．

中国式剰余定理

定理7中国式剰余定理

$a,b$ を整数， $m,n$ を互いに素な正の整数とするとき， $x\equiv a\pmod m$ かつ $x\equiv b\pmod n$ を満たす整数 $x$ は， $mn$ を法としてただ1つ定まる．

例えば，3で割ると2余り，5で割ると3余る整数 $x$ は， $x\equiv8\pmod15$ ，すなわち $8,23,38,\dots$ である．

フェルマーの小定理

定理8フェルマーの小定理

$p$ を素数とし，整数 $a$ が $p$ の倍数でないとき

$a^p-1\equiv1\pmod p$

が成り立つ．

例えば， $p=7$ ， $a=2$ のとき， $2⁶=64=7・9+1$ であるから $2⁶\equiv1\pmod7$ となる．

最終更新: 2026-08-12

この節についてAIに質問する

この節に書かれている内容だけを根拠に答えます。個人情報は書かないでください。

質問の内容