フェルマーの小定理

\(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\)という結論が得られることになります(つまりこの解答の略記が上の解答)。

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

 

不定方程式

次の不定方程式の整数解を求めよ.\[(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\)

【解答終】

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

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