合同式
$高校の数学Aで$
$整数 \ a,\ b\ を正の整数 \ m\ で割った余りをそれぞれ \ r,\ r'\ とすると$
$\quad $(i) $\ \ a \pm b \ を \ m\ で割った余りは \ \ r \pm r' \ \ を \ m\ で割った余りに等しい。$
$\quad $(ii)$\ \ ab \ を \ m\ で割った余りは \ \ rr' \ \ を \ m\ で割った余りに等しい。$
$\quad $(iii)$\ \ a^k \ (kは正の整数 )\ を \ m\ で割った余りは \ \ r^k\ を \ m\ で割った余りに等しい。$
$ことを学びますが、証明はいたって簡単です。$
$整数 \ a,\ b\ を正の整数 \ m\ で割った商と余りをそれぞれ \ \ q,\ q',\ r,\ r' \ \ (0 \leqq r,\ \ r' < m ) \ とすると$
$\quad a=mq+r ,\quad b=mq'+r' \ \ とおけます。$
(i)$\ は \quad a \pm b=m(q \pm q')+r \pm r' \ \ だから$
$\quad \ a \pm b \ を \ m\ で割った余りは、r \pm r' \ を \ m\ で割った余りに等しくなります。$
(ii)$\ は \quad ab=(mq+r)(mq'+r')=m(mqq'+qr'+q'r)+rr' \ \ だから$
$\quad ab\ を \ m\ で割った余りは、rr' \ を \ m\ で割った余りに等しくなります。$
(iii)$\ は$(ii)$で \ b=a \ とおくと a^2\ を \ m\ で割った余りは、r^2\ を \ m\ で割った余りに等しくなり$
$\quad これを繰り返して、一般に \ k\ を正の整数とすると$
$\quad \ a^k\ を \ m \ で割った余りは、r^k \ を \ m\ で割った余りに等しくなります。$
$また、これは教科書では研究という扱いになるのですが$
$\quad m\ を正の整数とし、2\ つの整数 \ a,\ b\ について$
$\qquad a-b \ が \ m\ の倍数であるとき、a\ と \ b\ は \ m\ を法として合同といい$
$\hspace{4em} a \equiv b \ \ (mod \ \ m)$
$\quad と書き、このような式を合同式という。$
$三角形や図形の合同も同じ「\equiv 」記号をもちいますが、これは整数論の話で内容は全く異なります。$
$合同式には次のような性質があります。$
$\hspace{1em} m\ を法として \ \ a \equiv r,\ \ b \equiv r' \quad ならば$
$\quad $(i)$\ \ a \pm b \equiv r \pm r'$
$\quad $(ii)$\ \ ab \equiv rr'$
$\quad $(iii)$\ \ a^k \equiv r^k \ \ (kは正の整数)$
$これらの証明もいたってシンプルです。$
$q,\ q'\ を整数として \quad a-r=mq,\quad b-r'=mq' \ \ とおけるから$
(i)$は$
\begin{eqnarray*} & &(a \pm b)-(r \pm r')\\ \\ &=&(a-r) \pm (b-r')\\ \\ &=&mq \pm mq'\\ \\ &=&m(q \pm q') \end{eqnarray*}
(ii)$は$
\begin{eqnarray*} & &ab-rr'\\ \\ &=&a(b-r')+r'(a-r)\\ \\ &=&amq'+r'mq\\ \\ &=&m(aq'+r'q)\\ \end{eqnarray*}
(iii)$は$
$\qquad $(ii)$で \ \ b=a,\ r'=r \ とおくと \ \ a^2 \equiv r^2$
$\qquad これと\ \ a \equiv r \ \ について再び$(ii)$を用いて \ \ a^3 \equiv r^3$
$\qquad これを繰り返して \quad a^k \equiv r^k$
$実は、上の2つの$(i)(ii)(iii)$の内容は全く同じです。$
$定理$
$\quad a \equiv b \ \ (mod \ \ m)\ \ と \ \ a,\ bを \ m\ で割った余りが等しいことは同値である。$
$→の証明$
$\hspace{2em}a,\ b\ を \ m\ で割った商と余りをそれぞれ \ q,\ q',\ r,\ r'\ \ (\ 0 \leqq r,r' < m \ )\ \ とおくと$
$\hspace{2em}a=mq+r,\quad b=mq'+r' \ \ だから\ \ a-b=m(q-q')+r-r'$
$\hspace{2em}a \equiv b \ \ (mod \ \ m) \ \ ならば a-b \ は \ m\ の倍数だから$
$\hspace{2em}r-r'=a-b-m(q-q') \ \ は \ m\ の倍数である。$
$\hspace{2em}ところが \quad -m < r-r' < m \ \ だから \ \ r-r'=0 \quad \therefore \ \ r=r'$
$←の証明$
$\hspace{2em}a,\ bを \ m\ で割った余りが等しいならば$
$\hspace{2em}a=mq+r,\quad b=mq'+r \ \ (0 \leqq r < m)\ \ とおけるから$
$\hspace{2em}a-b=m(q-q')\ \ となって \ a-b\ は \ m\ の倍数である。$
$一般に次の定理が成りたつ$
$\hspace{1em} n\ を法として \quad a \equiv b,\quad c \equiv d \quad ならば$
(i)$\ \ a \pm c \equiv b \pm d$
(ii)$\ \ ac \equiv bd$
(iii)$\ \ k\ が正の整数のとき \quad a^k \equiv b^k $
(ii)$の証明は$
$a-b=pn,\ \ c-d=qn \ \ (p,\ q\ は整数)\ \ とおけるから$
$ac-bd=(a-b)c+(c-d)b=pnc+qnb=(pc+qb)n$
(iii)$の証明は$
(ii)$をつかって \ \ a \equiv b\ \ を \ k\ 回辺々かければよい。$
$合同式を数学Aで全面的に扱うのは無理があるとの判断でしょうが、余りが前面に出てきませんので、$
$使い勝手がいいと思われます。$
$これらの性質を利用すると \quad a^k\ を \ m\ で割った余りを求めることができます。$
$例１ \quad 2^{10}\ \ を \ 7\ で割った余り$
$\hspace{2em} 7\ を法として \hspace{2em} 2^3=8 \equiv 1\ \ だから \quad 2^{10}=(2^3)^3 \times 2 \equiv 1^3 \times 2=2$
$例2 \quad 2018^{2018}\ \ を \ 10\ で割った余り(一の位の数)$
$\hspace{2em} 10\ を法として \hspace{2em} 2018 \equiv 8 \ \ だから \quad 2018^{2018} \equiv 8^{2018}$
$\hspace{3em} 8^2 \equiv 4 ,\ \ 8^3 \equiv 8 \times 4 \equiv 2 ,\ \ 8^4 \equiv 8 \times 2 \equiv 6,\ \ 8^5 \equiv 8 \times 6 \equiv 8 ,\ \ 8^6 \equiv 8 \times 8 \equiv 4,\ \ \cdots$
$\qquad となって、以下周期 \ 4\ で繰返します。$
$\qquad とくに、8^k \equiv 4\ となるのは \ \ k=2,\ 6,\ 10,\ \cdots \ \ ですから$
$\hspace{4em} k=2+(n-1)\times 4=4n-2 \quad のときです。$
$\hspace{4em} 2018=4 \times 505-2 \quad だから \quad 8^{2018} \equiv 4$
$\qquad ゆえに \quad 2018^{2018}\ \ を \ 10\ で割った余りは \ \ 4$
メインメニュー に戻る