カテゴリー: 合同式

「余り」がらみの問題では合同式が使えると見通しよく解けることが少なくありません。が，合同式を未習の生徒は非常に多い。そんなとき，簡単のため「まあ要は余りが等しいもの同士を\(\equiv\)で結ぶんだよ～」とざっくり紹介していますが厳密には違います。合同式の定義は

です。なので

を証明する必要があります。

証明

\(\Leftarrow\)は明らかであるから，\(\Rightarrow\)を示す．
\[a=pq_1+r_1,~b=pq_2+r_2\quad (0\leq r_1,r_2< p)\]とおくと，仮定により\((pq_1+r_1)-(pq_2+r_2)=pk~(k\in \mathbb{Z})\)と表せる．
\begin{align*}
&(pq_1+r_1)-(pq_2+r_2)=pk\Longleftrightarrow~p(q_1-q_2-k)=r_2-r_1
\end{align*}したがって\(r_2-r_1\)は\(p\)の倍数．ここで\(0\leq r_1,r_2< p\)より\(-p < r_1-r_2 < p\)であるから，\[r_2-r_1=0\]すなわち\(r_1=r_2\)．

証明終

まあ，同値ですから「余りが等しい」ことを「定義」とするという立場をとってもいいのかも知れませんが。。

合同式の問題でよく見る問題です。

解答

\begin{align*}
11^{10}&\equiv 2^{10}\\
&\equiv 2\cdot 2^9\\
&\equiv 2\cdot 8^3\\
&\equiv 2\cdot (-1)^3\\
&\equiv -2\\
&\equiv 7 \pmod 9
\end{align*}よって\[11^{10}\equiv 7 \pmod 9\]したがって求める余りは\(7\)

解答終

授業でこの解説をしたところ「\(\equiv\)を\(=\)の同じような使い方をしてよいのかどうかがいまいちしっくりこない」という感想が。そう言われてみれば確かにこの解説はちょっと乱暴過ぎます（理解に必要な準備が足らない）。以下，この解答の理解のために知識を追加します。

まず一つ目。\[a_1 \equiv a_2 \equiv a_3 \equiv \cdots \equiv a_n \pmod p\]を\[a_1 \equiv a_2 \pmod p,~a_2 \equiv a_3\pmod p,~\cdots~,a_{n-1} \equiv a_n \pmod p\]を意味するものと規約します。これはただの記法なので問題なし。

二つ目。\[a_1 \equiv a_2 \equiv a_3 \equiv \cdots \equiv a_n \pmod p~\text{ならば}~a_1 \equiv a_n \pmod p\]であることを確認します。これは結局，次の性質（推移律）があるのか？という問題に帰着します。

証明

仮定により\(a-b=pk,b-c=pk^{\prime}\Longleftrightarrow a=b+pk,~b=c+pk^{\prime}\)．このとき，
\begin{align*}
a-c&=b+pk-c\\
&=c+pk^{\prime}+pk-c\\
&=p(k^{\prime}+k)
\end{align*}よって\[a\equiv c\pmod p\]

証明終

以上により，上の解答の式は
\begin{align*}
&11^{10}\equiv 2^{11}\pmod 9\\
&2^{11}\equiv 2\cdot 2^9\pmod 9\\
&2\cdot2^9\equiv 2\cdot 8^3\pmod 9\\
&2\cdot 8^3\equiv 2\cdot (-1)^3\pmod 9\\
&2\cdot (-1)^3\equiv -2\pmod 9\\
&-2\equiv 7 \pmod 9
\end{align*}を意味し，上で示した性質（推移律）を繰り返し適用することにより\(11^{10}\equiv 7 \pmod 9\)という結論が得られることになります（つまりこの解答の略記が上の解答）。

「わからない」「しっくりこない」という素直な感覚は，理解を深めるひとつの起点であると改めて思ます。

\(a\equiv b\pmod p,~c\equiv d\pmod p\)のとき，\[a\pm c \equiv b \pm d\pmod p,~ac \equiv bd\pmod p,~a^n \equiv b^n\pmod p\]が成り立つことは教科書や問題集等でよく証明されているので，ここではあまり紹介されないもののよく使う次の式を証明してみます。前半は片方のみに法の整数倍を加えるという\(=\)の世界では決して許されなかった計算が許されるという性質，後半は逆に\(\equiv\)の世界では禁じ手であった「両辺を割る」という操作ががある仮定のもとに限り許されるという面白い性質です。

証明

仮定により\(a-b=pk\)であるから
\begin{align*}
a-(b+kp)&=pk+b-(b+kp)\\
&=pk+kp=p(k+1)
\end{align*}よって\[a\equiv b+pk \pmod p~(k\in \mathbb{Z})\]

証明終

証明

仮定により\[ac-bc=pk \Longleftrightarrow (a-b)c=pk\]右辺が\(p\)の倍数であるから左辺も\(p\)の倍数．ここで，\(c\)が\(p\)の倍数（\(c=pk^{\prime}\)）であると仮定すると，\(c(=pk^{\prime})\)と\(p\)が互いに素であることに反する（合同式の定義により\(p\)は\(2\)以上のの整数であることに注意）．したがって\(a-b\)が\(p\)の倍数，すなわち\[a\equiv b \pmod p\]
証明終

教科書と同じ解法はつまらないので，合同式を用いて解いてみます。

解答

\((1)\)
\[7x-17y\equiv1\pmod{7}\]
左辺に\(7(-x)\)を加えて（ア）
\[-17y\equiv1\pmod{7}\]
左辺に\(14y\)を加えて
\[-3y\equiv1\pmod{7}\]
両辺を\(2\)倍して（イ）
\[-6y\equiv2\pmod{7}\]
左辺に\(7y\)を加えて
\[y\equiv2\pmod{7}\]
よって\[y=7k+2~(k\in\mathbb{Z})\]
もとの式にこれを代入して
\[x=17k+5~(k\in\mathbb{Z})\]

\((2)\)
\[52x+539y\equiv19\pmod{52}\]
左辺に\(52(-x)\)を加えて
\[539y\equiv19\pmod{52}\]
左辺に\(52(-10y)\)を加えて
\[19y\equiv19\pmod{52}\]
\(19\)と\(52\)は互いに素であるから，両辺を\(19\)で割ることができて（ウ）
\[y\equiv1\pmod{52}\]
よって\[y=52k+1~(k\in\mathbb{Z})\]
もとの式にこれを代入して
\[x=-539k-10~(k\in\mathbb{Z})\]

解答終

このように合同式を利用すればゴチャゴチャ計算しなくとも簡潔に記述できます。
ただし（ア）（イ）（ウ）の操作は証明が必要です。