高校数学：整数：合同式の性質と使い方

こんにちは。知っておくと便利な合同式。その性質と証明と使い方を書いておきます。早速やっていきましょう。

合同式とは

ある整数 $a, b$ を整数 $m$ を割ったときの余りが等しいとき, $a$ と $b$ は $m$ を法として合同( $m$ で割った余りが等しい)と言います。
例えば, 14と8を6で割ったときの余りはともに2ですから, 14と8は6を法として合同(6で割った余りが等しい)と言います。
これを数学の記号では,
$14\equiv8\ (\text{mod}\ 6)$
読み方は
「14合同8モッド6」と読みます。
と書きます。
$\text{mod}$ ～とは～で割った余りということです。
他に7と10は3で割ると余りがともに1なので, $7\equiv10\ (\text{mod}\ 3)$ となります。

合同式の性質

$a\equiv b$ , $c\equiv d$ ならば,
$\maru1$ 和　 $a+c\equiv b+d\ (\text{mod}\ m)$
$\maru2$ 差　 $a+c\equiv b+d\ (\text{mod}\ m)$
$\maru3$ 積　 $ac\equiv bd\ (\text{mod}\ m)$
$\maru4$ 商　 $ea\equiv eb\ (\text{mod}\ m)$ $e$ と $m$ は互いに素ならば, $a\equiv b$
$\maru5$ 累乗　 $a^n\equiv b^n\ (\text{mod}\ m)$ $n$ は自然数
が言えます。

以下 $m$ を法として話を進めていきます。特に断りのない場合はすべて $\text{mod}\ m$ です。
また, $a\equiv b$ なので,
$a=mp+r$ , $b=mq+r$ とし,
$b\equiv d$ なので,
$c=ms+r'$ , $d=mt+r'$ とする。
ただし, $p, q, r, r', s, t$ は整数とする。

①の証明

$a+c\equiv b+d$ の証明
$\begin{array}{lll}a+c&=&(mp+r)+(ms+r')\\&=&m(p+s)+r+r'\equiv r+r'\ (\text{mod}\ m)\\\end{array}$
$\begin{array}{lll}b+d&=&(mq+r)+(mt+r')\\&=&m(q+t)+r+r'\equiv r+r'\ (\text{mod}\ m)\\\end{array}$
以上より, $m$ で割った余りが等しいので,
$a+c\equiv b+d\ (\text{mod}\ m)$

②の証明

$a-c\equiv b-d$ の証明
$\begin{array}{lll}a-c&=&(mp+r)-(ms+r')\\&=&m(p-s)+r-r'\equiv r-r'\ (\text{mod}\ m)\\\end{array}$
$\begin{array}{lll}b-d&=&(mq+r)-(mt+r')\\&=&m(q-t)+r-r'\equiv r-r'\ (\text{mod}\ m)\\\end{array}$
以上より, $m$ で割った余りが等しいので,
$a-c\equiv b-d\ (\text{mod}\ m)$

③の証明

$ac\equiv bd$ の証明
$\begin{array}{lll}ac&=&(mp+r)(ms+r')\\&=&m^2ps+(pr'+sr)m+rr'\equiv rr'\ (\text{mod}\ m)\\\end{array}$
$\begin{array}{lll}bd&=&(mq+r)(mt+r')\\&=&m^2qt+(qr'+tr)m+rr'\equiv rr'\ (\text{mod}\ m)\\\end{array}$
以上より, $m$ で割った余りが等しいので,
$ac\equiv bd\ (\text{mod}\ m)$

④の証明

$ea\equiv eb\ (\text{mod}\ m)$ $e$ と $m$ は互いに素ならば, $a\equiv b$ の証明
$ea\equiv eb$ なので,
$ea-eb=e(a-b)=\equiv 0\ (\text{mod}\ m)$ より,
$e(a-b)$ は $m$ の倍数。
また, $e$ と $m$ は互いに素なので,
$a-b$ が $m$ の倍数である。
よって, $a-b\equiv0$
つまり, $a\equiv b\ (\text{mod}\ m)$
互いに素でなければ,
例えば, $14\equiv8\ (\text{mod}\ 6)$ の辺々を2で割ると, $7\equiv4\ (\text{mod\ 6})$ となり合同が成り立ちません。
互いに素であるなら,
例えば, $14\equiv8\ (\text{mod}\ 3)$ の辺々を2で割っても, $7\equiv4\ (\text{mod\ 3})$ となり合同が成り立ちます。

⑤の証明

$a^n\equiv b^n$ の証明
二項定理を用いて展開していきます。
$\begin{array}{lll}a^n&=&(mp+r)^n\\&=&{}_n\text{C}_0(mp)^nr^0+{}_n\text{C}_1(mp)^{n-1}r^1+{}_n\text{C}_2(mp)^{n-2}r^2+\cdots+{}_n\text{C}_n(mp)^0r^n\\&\equiv&r^n\ (\text{mode}\ m)\end{array}$
$\begin{array}{lll}b^n&=&(mq+r)^n\\&=&{}_n\text{C}_0(mq)^nr^0+{}_n\text{C}_1(mq)^{n-1}r^1+{}_n\text{C}_2(mq)^{n-2}r^2+\cdots+{}_n\text{C}_n(mq)^0r^n\\&\equiv&r^n\ (\text{mode}\ m)\end{array}$
以上より, $m$ で割った余りが等しいので,
$a^n\equiv b^n\ (\text{mod}\ m)$

合同式の使い方の例

【例】 $n$ は6で割って4余る整数です。このとき, $n^2+5n+3$ を6で割った余りを求めなさい。

合同式を用いない場合は, $n=6k+4$ とおいて代入していって計算していくのがお決まりである。
今回はそうではなく, 余りに着目して解くとどうなるかということである。
$n$ を6で割った余りが4なので
$n\equiv4\ (\text{mod}\ 6)\cdots\maru1$
合同式は累乗できるので, $\maru1$ の辺々2乗して
$n^2\equiv16\cdots\maru2$
合同式は掛け算できるので, $\maru1$ の辺々5倍( $5\equiv5$ を掛ける)して,
$5n\equiv20\cdots\maru3$
$3\equiv3\cdots\maru4$
$\maru2+\maru3+\maru4$ とすると,
$n^2+5n+3\equiv16+20+3=39\equiv3\ (\text{mod}\ 6)$
したがって, 求める余りは3

【例】 $4^{100}$ を13で割った余りを求めよ。

$4^3=64$ でこのとき, 13で割ると余りが $-1$ になります。これを使うと次のようになります。
$4^3=64\equiv-1\ (\text{mod}\ 13)$
求めるのは100乗なので, 辺々33乗して4をかけると,
$\left(4^3\right)^{33}\cdot4\equiv(-1)^{33}\cdot4\ (\text{mod}\ 13)$
$4^{100}\equiv-4\equiv9\ (\text{mod}\ 13)$
よって, 求める余りは9
※余り $-4$ ということは, 余り9と合同