【応用】合同式

🕒 2018/08/02 🔄 2023/05/01

ここでは、整数同士の和・差・積によって余りがどうなるかを復習した後、余りだけに着目したい場合に便利な合同式について見ていきます。

📘 目次

整数の和や積と余り

まずは、【基本】整数の和や積と余り#おわりにで見た内容を、一般的な場合で確認していきます。

整数 $a_1,a_2$ を正の整数 $m$ で割ったときの商をそれぞれ $q_1,q_2$ とし、余りを $r_1,r_2$ とします。このとき、\[ a_1=mq_1+r_1,\ a_2=mq_2+r_2 \]となります。和について考えると、
\begin{eqnarray} a_1+a_2 &=& (mq_1+r_1)+(mq_2+r_2) \\[5pt] &=& m(q_1+q_2)+(r_1+r_2) \\[5pt] \end{eqnarray}となり、 $q_1+q_2$ は整数だから、 $a_1+a_2$ を $m$ で割った余りは、 $r_1+r_2$ を $m$ で割った余りと等しいことがわかります。また、差も\[ a_1-a_2=m(q_1-q_2)+(r_1-r_2) \]となるので、 $a_1-a_2$ を $m$ で割った余りは、 $r_1-r_2$ を $m$ で割った余りと等しくなります。

積についても同じように計算すると
\begin{eqnarray} a_1a_2 &=& (mq_1+r_1)(mq_2+r_2) \\[5pt] &=& m^2q_1q_2+mq_1r_2+mq_2r_1+r_1r_2 \\[5pt] &=& m(mq_1q_2+q_1r_2+q_2r_1)+r_1r_2 \\[5pt] \end{eqnarray}となり、 $mq_1q_2+q_1r_2+q_2r_1$ は整数だから、 $a_1a_2$ を $m$ で割った余りは、 $r_1r_2$ を $m$ で割った余りと等しくなります。

このように、余りだけに注目すれば、和・差・積によって、余りが変わらないことがわかります。

合同式

上で見たような、「余りだけに注目したい」場合に、毎回「 $m$ で割った余り」と書くと、すごく長くなってしまいます。そこで、合同式 というものを用いて、次のように簡潔に表すことがあります。

合同式

$m$ を正の整数とする。整数 $a,b$ を $m$ で割った余りが等しいとき、「 $a,b$ は $m$ を法として合同である」(congruent modulo $m$ ) といい、次のように表す。\[ a \equiv b \pmod m \]この式を、合同式という。

$a \equiv b \pmod m$ は、「 $a-b$ が $m$ の倍数である」と言い換えることもできます。

合同式は、高校で一般的に扱う内容ではありませんが、難関大学の入試などでは、知っておくと便利なことがあります。以下では、基本的な性質を見ていきましょう。

まず、式変形などで使える次の3つは、定義から考えると、当然成り立つことはわかると思います。

合同式の基本的な性質

$m$ を正の整数とする。整数 $a,b,c$ について、次が成り立つ。

$a \equiv a \pmod m$
$a \equiv b \pmod m$ ならば、$b \equiv a \pmod m$
$a \equiv b \pmod m$, $b \equiv c \pmod m$ ならば、$a \equiv c \pmod m$

また、冒頭で見た、和・差・積の余りについて見た内容から、次のことが言えます。

和・差・積と合同式

$m,k$ を正の整数とする。 $a,b,c,d$ は整数で、 $a \equiv c \pmod m$, $b \equiv d \pmod m$ を満たすとき、次が成り立つ。

$a+b \equiv c+d \pmod m$
$a-b \equiv c-d \pmod m$
$ab \equiv cd \pmod m$
$a^k \equiv c^k \pmod m$

例えば、 $a\equiv c \pmod m$ というのは、 $m$ で割った余りが同じということなので、 $a=qm+c$ となる整数 $q$ が存在することと同じです。ということは、冒頭で見たのとほぼ同じ式変形で、1つ目から3つ目の式を確かめることができます。

4つ目は、3つ目から導けます。3つ目の式で $b=a$, $d=c$ とすると、 $a^2 \equiv c^2 \pmod m$ となります。これをさらに利用して、3つ目の式で $b=a^2$, $d=c^2$ とすると、 $a^3 \equiv c^3 \pmod m$ となります。以下、繰り返していけば、4つ目が成り立つことがわかります。

最後に、合同式によって計算が簡単になる例を見ておきましょう。例えば、 $100^{100}$ を $7$ で割った余りを考えてみましょう。まじめに計算するのは大変です。しかし、合同式を使えば、\[ 100\equiv 2 \pmod 7 \]なのだから、 $100^{100}$ の代わりに $2^{100}$ を考えればいいですね。まだ計算は大変ですが、\[ 2^{100}=2\times 2^{3\times 33}=2\times 8^{33} \]と変形してみましょう。そうすると、 $8\equiv 1 \pmod 7$ となるため、 $8^{100} \equiv 1^{100} \pmod 7$ となり、実質考えなくてよくなります。まとめると
\begin{eqnarray} 100^{100} & \equiv & 2^{100} \pmod 7 \\[5pt] & \equiv & 2\times 8^{33} \pmod 7 \\[5pt] & \equiv & 2 \pmod 7 \end{eqnarray}となり、余りは $2$ だとわかります。

合同式では、上のように $1^k$ や $(-1)^k$ を作り出すように変形すると、余りがサクッと求められるようになります。合同式の便利な点はいくつもありますが、ここで見た内容はその一例です。