整数問題 (特に剰余に関わる問題) で絶大な威力を発揮する合同式の基礎事項について解説します．
整数問題の中でも特によく出題されるのが剰余に関わる問題です．剰余とは余りのことで，たとえば，『$2^{40}$ を $7$ で割った余りを求めよ．』などのように余りを問う問題がよくあります．また，不定方程式の整数解を求める際にも，剰余の考え方を用いることで，解を絞れることがあります．
整数そのものより，むしろその整数の余り (剰余) の方に関心がある場合は合同式を用いると便利です．簡単に言えば，整数全体をある数で割った余りで分類し，余りが同じ整数はすべて同じ (合同) とみなすのです．
合同記号の記述方法を説明します．
整数 $a$ と $b$ を 整数 $m$ で割った余りが等しいとき，$a$ と $b$ は $m$ を法として合同といい， $$a \equiv b ~~~(\rm{mod}\ m)$$ とかく．
$a$ と $b$ を三本線で結び，何で割った余りなのかわかるように，式の右側に ($\rm{mod}$〜) とかくのが慣習です．
$\rm{mod}\ m$ の $\rm{mod}$ というのは $modulo$ の略です．
例 ・$4 \equiv 2 (\rm{mod}\ 2)$ ・$13 \equiv 1 (\rm{mod}\ 3)$ ・$8 \equiv 0 (\rm{mod}\ 4)$ ・$5 \equiv -1 (\rm{mod}\ 6)$
・$1234 \equiv 2 (\rm{mod}\ 7)$
整数 $a$ と $b$ を 整数 $m$ で割った余りが等しいというのは，$a-b$ が $m$ の倍数ということと同値です．こちらの言い方のほうがわかりやすいかもしれません．一番最後の例を見るとわかるように，どれほど大きな数でも余りに関しては割る数より小さくできます．これが剰余を考えることのメリットです．
合同式に関して次の基本的性質が成り立ちます．
$m$ を整数とする．$a \equiv b,\ c \equiv d~~~(\rm{mod}\ m)$ のとき，次が成り立つ． ($1$) $a+c \equiv b+d~~~(\rm{mod}\ m)$ ($2$) $a-c \equiv b-d~~~(\rm{mod}\ m)$ ($3$) $ac \equiv bd~~~(\rm{mod}\ m)$ ($4$) $a^n \equiv b^n~~~(\rm{mod}\ m)$ ($n$ は自然数)
要するに，加法，減法，乗法を行っても合同を保ちます．よく使うのが ($4$) です．後の例題でその使い方を解説します．ところで，注意すべきことは，除法では，一般に合同を保たないということです．たとえば， $$12 \equiv 24~~~(\rm{mod} 6)$$ ですが，両辺を $4$ で割って， $$3 \equiv 6~~~(\rm{mod} 6)$$ などとすることはできません．実際，$3$ と $6$ は $6$ を法として合同ではありません．一般に，除法に関しては次のことが成り立ちます．
$ac \equiv bc~~~(\rm{mod}\ m)$ のとき，$c$ と $m$ が互いに素ならば，$a \equiv b~~~(\rm{mod}\ m)$ が成り立つ．
つまり，割る数と法が互いに素でないと，除法が安心して行えません．
問 $2^{40}$ を $7$ で割った余りを求めよ．
$2^{40}$ を計算してから筆算で $7$ で割った余りを求めるのは面倒です．$40$ 乗という指数部分を計算する前に，合同式を用いて $2^{40}$ を簡単な数にしてしまおうというのが基本的なアイデアです．
$2^3=8 \equiv 1~~~(\rm{mod}\ 7)$ です．ここで，自然数 $n$ に対して， $$(2^3)^n \equiv 1^n=1$$ です．$2^{40}=2\times (2^3)^{13}$ なので， $$2^{40}=2\times (2^3)^{13} \equiv 2\times 1=2~~~(\rm{mod}\ 7) $$ よって，$2^{40}$ を $7$ で割った余りは $2$.
この問題では， $2^3$ を $7$ で割った余りが $1$ となったので，簡単に余りを求めることができました．このように，与えられた式の一部が合同式の意味で $1$ や $-1$ や $0$ などの簡単な数になってくれれば，その式がかなり簡単になるので，簡単になる部分を探すというのがポイントになります．もう一つ簡単な例題を見てみましょう．
問 $5^{2016}$ を $13$ で割った余りを求めよ．
決して $5^{2016}$ を計算しようとしないでください．計算する必要はないのです．まず，$5^{2016}$ の部分のうち，$13$ で割って簡単になる部分を探します．すると，$5^2=25 \equiv -1~~~(\rm{mod}\ 13)$ ということに気づきます．ここがポイントです．
$5^2=25 \equiv -1~~~(\rm{mod}\ 13)$ です．したがって， $$5^{2016}=(5^2)^{1008} \equiv (-1)^{1008}=1~~~(\rm{mod}\ 13)$$ よって，$5^{2016}$ を $13$ で割った余りは $1$.
このように，負の数を利用すると，計算が簡単になります．基本的には，$1,0,-1$ などと合同な部分を探して，与えられた数を丸め込んでやるとうまくいくことが多いです．
まだまだ合同式に関しては多くの重要な事実があるので，徐々にステップアップしていきましょう．
