合同式の定義とその直観的解釈

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

\[a\equiv b \pmod{p} \overset{\text{def}}{\Longleftrightarrow} \exists k\in\mathbb{Z}[a-b=pk]\]

です。なので

\[\exists k\in\mathbb{Z}[a-b=pk] \Longleftrightarrow \text{\(a\)を\(p\)で割った余りと\(b\)を\(p\)で割った余りが等しい}\]

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

証明

\(\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\).

証明終

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

合同式の応用

    1. \(10^{10}\)を\(2020\)で割った余りを求めよ。
    2. \(100\)桁の正の整数で各位の数の和が\(2\)となるもののうち,\(2020\)で割り切れるものの個数を求めよ。
  • (一橋大)

    解答

    \(2020\)を法として考える.以下,\(\mod 2020\)を省略して記述する.
    \(10000\equiv10000+2020\cdot(-5)\equiv-100\)であるから
    \begin{align*}
    10^{10}\equiv&10^2\cdot(10^4)^2\\
    \equiv &10^2\cdot(-100)^2\\
    \equiv &10^2\cdot10000\\
    \equiv &10^2\cdot(-100)\\
    \equiv &-10000\\
    \equiv &-(-100)\\
    \equiv &100
    \end{align*}

    ゆえに\(10^{10}\equiv100\)(\(1.\)の答え

    \(100\)桁の正の整数で各位の数の和が\(2\)であるような数は
    \begin{align*}
    \mathrm{(i)}\quad &2\underbrace{0\cdots0}_{99\text{個}}=2\times10^{99}\\
    \mathrm{(ii)}\quad &1\underbrace{0\cdots01\overbrace{0\cdots0}^{k\text{個}}}_{99\text{個}}=10^{99}+10^k\quad(0\leq k \leq 98)
    \end{align*}のいずれかである.

    \(\mathrm{(i)}\)のとき
    \(1.\)により\(10^{10}\equiv10^2\)であることに注意して,
    \begin{align*}
    2\times10^{99}\equiv&2\cdot10^{9}\cdot(10^{10})^9\\
    \equiv&2\cdot10^{9}\cdot(10^{2})^9\\
    \equiv&2\cdot 10^{27}\\
    \equiv&2\cdot(10^{10})^2\cdot10^7\\
    \equiv&2\cdot(10^{2})^2\cdot10^7\\
    \equiv&2\cdot10^{11}\\
    \equiv&2\cdot10^{10}\cdot10\\
    \equiv&2\cdot10^{2}\cdot10\\
    \equiv&2000\\
    \end{align*}ゆえにこの数は\(2020\)で割り切れない.

    \(\mathrm{(ii)}\)のとき
    \(10^{99}+10^{k}\equiv 1000 + 10^{k}\)より(なぜならば\(\mathrm{(i)}\)の途中過程により\(10^{99}\equiv1000\)),\(1000+10^k\equiv 0(\Leftrightarrow 10^{k}\equiv -1000)\)を満たす\(k~(0\leq k \leq 98)\)の個数を調べればよい.\(k\)の値は高々\(99\)個なので,実際に調べてみると(やる気),

     

    \(1,10\)から始まり,\(100,1000,-100,-1000\)と繰り返すことがわかる.したがって,\(99=2+4\times 24+1\)により求める個数は\(24\)個とわかる.(\(2.\)の答え

    解答終

    フェルマーの小定理

    \(p\)を素数とする.整数\(a\)が\(a \not\equiv 0 \pmod p\)をみたすならば,\[a^{p-1} \equiv 1 \pmod p\]が成り立つ.

    証明

    \[1a,~2a,~3a,~\cdots,(p-1)a\]を考える.これらを\(p\)で割った余りはすべて異なることを以下に示す.\(p\)で割って余りが等しくなるような\(2\)数が存在すると仮定し,それらを\(ia,ja~(1 \leq i,j \leq p-1,~i\neq j )\)とおけば\[ia\equiv ja \pmod p \Longleftrightarrow (i-j)a\equiv 0 \pmod p\]が得られるが,\(a \not\equiv 0 \pmod p\)により\(i-j \equiv 0 \pmod p\)でなくてはならない.しかし,\(1 \leq i,j \leq p-1\)であったから,\(i-j\)は\(p-1\)以下であり,矛盾する.

    したがって\(1a,~2a,~3a,~\cdots,(p-1)a\)を\(p\)で割った余りはすべて異なる.また\(a\not \equiv 0 \pmod p\)よりこれらは\(p\)では割り切れない(\(p\)で割っても余りが\(0\)にはならない)から,\(1a,~2a,~3a,~\cdots,(p-1)a\)を\(p\)で割ると余りとして\(1,2,\cdots,p-1\)がそれぞれ\(1\)回ずつ現れることになる.これを\[1a\equiv n_{1}~,2a\equiv n_{2}~,~\cdots~,(p-1)a\equiv n_{p-1}\]と表すことにする(ただし\((n_{1},~n_{2},~\cdots~,n_{p-1})\)は\(1,2,~\cdots~,p-1\)の適当な順列).辺々掛けることで
    \begin{align*}
    &1\cdot 2 \cdot \cdots \cdot (p-1) a^{p-1}\equiv n_{1}n_{2}\cdots n_{p-1} \pmod p \\
    \Longleftrightarrow ~&(p-1)! a^{p-1}\equiv (p-1)! \pmod p
    \end{align*}ここで,\(\gcd(p,(p-1)!)=1\)であるから(実際,\(p\)と\((p-1)!\)に共通な素因数が存在すると仮定すると,\(p\)が素数であることからその共通の素因数は\(p\)であるが,\(1,2,\cdots,p-1\)はいずれも\(p\)では割り切れず,矛盾する),両辺を\((p-1)!\)で割ることができて\[a^{p-1} \equiv 1 \pmod p\]が得られる.

    証明終

    「分からない」の大切さ

    \(11^{10}\)を\(9\)で割った余りを求めよ.

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

    解答

    \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\equiv b\pmod p \land b \equiv c \pmod p \Longrightarrow a\equiv c \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 \equiv b\pmod p\)のとき,\[a\equiv b+pk \pmod p~(k\in \mathbb{Z})\]

    証明

    仮定により\(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})\]

    証明終

    \(\gcd(c,p)=1\)(\(c\)と\(p\)が互いに素)のとき,
    \[ac \equiv bc \pmod p\Longrightarrow a \equiv b \pmod p\]

    証明

    仮定により\[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=1 \qquad (2)~52x+539y=19 \]

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

    解答

    \((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})\]

    解答終

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

    不定方程式の解法

    不定方程式の解法について考察してみます.

    不定方程式\[49x-23y=1\]の解となる最小の自然数\(x\)を答えよ.

    (2019 センター試験数学Ⅰ・A 改題)

    定石的には,ユークリッドの互除法により特殊解を見つけて,それを代入したものを辺々引いて・・・という手順を踏みますが,合同式を利用すれば

    【解答】

    以下,\(\mathrm{mod} 23\)とする.

    \[
    \begin{align*}
    &49x-23y\equiv1\\
    &49x\equiv1\\
    &3x\equiv1\\
    &24x\equiv8\\
    &x\equiv8\\
    \end{align*}
    \]

    したがって,一般解は\(x=23k+8\)(\(k\)は任意の整数)であるから答えは\(8\)

    【解答終】

    ・・・と,このようにスピーディーに解答できるので,ぜひマスターしておきたいところです.変形のイロハについてもいずれ記事にしたいと思ってます.塾でも希望者には合同式講座を開催しますので,ぜひ参加してください^^

    合同式の有用性

    数学Aの整数分野に「合同式」という話題があります.しかし,学校の授業だと時間の関係上割愛されることも多い.実際,僕も学校で授業するときは時間が一杯一杯で余裕がなく,ここはいつもとばしていました.そんなことをふと思い出したので,ちょっとこの話題について触れてみようと思います.

    数学検定1級の1次の問題に,こんな問題がありました.\[23^{23^{23}}\text{の第一位の数を答えよ}\]「第一位の数を求めろ」問題の定石は,おなじみ「実験して推測しろ」なので,少し実験してみることにします.一の位の数のみに着目して計算すると,\[3\rightarrow9\rightarrow7\rightarrow1\rightarrow3\rightarrow9\rightarrow7\rightarrow1\rightarrow\cdots\]となり,\[3,9,7,1\]を繰り返していることが分かります.これはいわば繰り返しの周期が4であることを示しているので,結局,\(23\)の冪(べきと読みます)\(23^{23}\)に周期4がいくつあるか,すなわち,\[23^{23}\text{を}4\text{で割った余りはいくらか}\]という問題に帰着します.ここで,合同式を利用すると以下のように数行で終わります.\[\begin{align}23^{23}&\equiv (-1)^{23} \\&\equiv -1 \\ &\equiv 3\end{align}\]ゆえに,\[23^{23}=4\times Q+3\]したがって,求める答えは周期の前から3番目,すなわち7と分かります.かんたん!

    このように合同式を学んでおくと解きづらい問題・考えづらい問題も明解に論述できることが少なくありません.というわけで,皆さんも合同式について学んでみてはいかがでしょうか.

    © 2024 佐々木数学塾, All rights reserved.