合同式の定義

「ある自然数 $n$ で割ったあまりが等しいものを同一視する」という世界が合同式の世界である。 例えば、自然数 $a$ と $b$ が自然数 $n$ で割ったあまりが等しいとき \[ a \equiv b \mod n \] とかく。あるいは$\,a-b\,$が$\,n\,$で割り切れる時 \[ a \equiv b \mod n \] とかくと定義しても同じことである。 この$\mod n\,$の世界では \[ n \equiv 0 \mod n \] が成立するから、$n$ を $0$ と同一視しようという世界が$\mod n\,$の世界なのだと見ることもできる。 余りさえ等しければ良いのであるから、これは通常の「=」の世界より緩い。つまり \[ a = b \] であれば当然 \[ a \equiv b \mod n \] が任意の自然数$n$について成立する。

合同式の性質

この合同式に用いられる記号「≡」はイコール記号「=」と同じような性質を持つ。 端的に言えば、割り算以外は「=」と同じように扱って良い。

反射律

\[ a \equiv a \mod n \]

対称律

\[ a \equiv b \mod n \quad \iff \quad b \equiv a \mod n \]

推移律

\[ a \equiv b \mod n \quad \mbox{かつ} \quad b \equiv c \mod n \] のとき \[ a \equiv c \mod n \] が成立。

足し算と引き算

\[ a \equiv b \mod n \quad \mbox{かつ} \quad c \equiv d \mod n \] のとき \[ a \pm c \equiv b \pm d \mod n \] が成立。

乗法

\[ a \equiv b \mod n \quad \mbox{かつ} \quad c \equiv d \mod n \] のとき \[ a \cdot c \equiv b \cdot d \mod n \] が成立。

上の性質からわかること

合同式において、$a\equiv b \mod n $ が成り立つとき、部分的に $a$ を $b$ で置き換えることができる。 例.$\mod 7$ で考える。 \[ 19 \equiv 5 \mod 7 \] \[ 17 \equiv 3 \mod 7 \] がそれぞれ成立する。このとき \[ 19 \cdot 17 \equiv 5\cdot 3 \mod 7 \] と計算することができる。さらに計算を進めると \[ 19 \cdot 17 \equiv 5\cdot 3 = 15 \equiv 1 \mod 7 \] となり、 \[ 19 \cdot 17 \equiv 1 \mod 7 \] が得られる。これは $19\cdot 17$ を $7$ でわったあまりは $1$ と等しいことを意味する。 実際に計算してみると \[ 19 \cdot 17 = 323 = 46\cdot7 + 1 \] となり、合同式を用いて得られた結果が正しいことが確認できる。

演習問題

問題. $2^{20}$ を $11$ で割ったあまりを求めよ。

解答. $2^{20}$ を直接計算するということはしない。 \[ 2^3 = 8 \equiv -3 \mod 11 \] に注目しよう。(補足. ここでは \[ 8 \equiv 8 - 0 \equiv 8-11 = -3 \] を利用している。) \begin{eqnarray*} 2^{20} = 2^{3\cdot 6 + 2} = (2^3)^6\cdot 2^2 & \equiv & (-3)^6 \cdot 4 \mod 11 \\ &= & 9^3 \cdot 4 \\ &\equiv & (-2)^3 \cdot 4 \mod 11 \\ &= & -8 \cdot 4 \\ &\equiv & 3 \cdot 4 \mod 11 \\ &= & 12 \\ &\equiv & 1 \mod 11 \end{eqnarray*} したがって \[ 2^{20} \equiv 1 \mod 11 \] が得られる。(Note. ところどころ「=」があるが、これは「$\equiv$」に置き換えることもできるから、 推移律によって、最初と最後を「$\equiv$」で結ぶことができる。)

別解. \[ 2^5 = 32 \equiv -1 \mod 11 \] に気づけばもっと計算が楽になる。 \begin{eqnarray*} 2^{20} &=& 2^{5\cdot 4} \\ &\equiv& (-1)^4 \mod 11 \\ &=& 1 \end{eqnarray*}

Note. オイラー関数を学習するとすぐに \[ 2^{10} \equiv 1 \mod 11 \] がわかるようになる。

センター試験(2019)に挑戦

ここまでの知識でセンター試験(2019)の不定方程式の問題に挑戦してみよう。
問題. \[ 49x-23y = 1 \] の解を求めよ。
解法. 解 $x$ を求めたい。そこで、$y$ は邪魔だから、$\hspace{-5pt}\mod 23$で考えて $y$ を消す. \[ 49x \equiv 1 \mod 23. \] 左辺の $x$ の係数 $49$ を $1$ にできれば $x$ について解けたことになる。 \begin{alignat}{2} && 49x \equiv 1 &\mod 23 \\ \iff \quad && 3x \equiv 1 &\mod 23 \\ \iff \quad && 8\cdot 3x \equiv 8 &\mod 23 \qquad (\mbox{両辺を8倍した.})\\ \iff \quad && 24x \equiv 8 &\mod 23 \\ \iff \quad && x \equiv 8 &\mod 23 \end{alignat} よって、 $x=8$ が一つの解であることが分かる。 ここで、ポイントは $8$ 倍したところだ。なぜ $8$ 倍したかというと、定数をかけて$24$に近づけようとしたからである。 $\hspace{-10pt} \mod 23 $ の世界では \[ 24 \equiv 1 \] であるから、「 $3$ を $1$ にしたい」ということは「 $3$ を $24$ にしたい」ということと同じことである。 だから、$8$ 倍するということが思いつく。 $y$ はこの解を用いると \[ 23y = 49x -1 = 49 \cdot 8 -1 = 391 \] であるから、素直に計算して \[ y = \frac{391}{23} = 17 \] として得られる。