フェルマーの小定理を高校数学で証明する。〜実際の入試ではどう使う？〜

入試では「 $719^{2021}$ の下二桁を求めよ。」といった、西暦に絡めた問題が出題されることがあります。（この記事の公開日は2021年7月19日です。）

この問題は、$719^{2021}$ を $100$ で割った余りが答えになるわけですが、真面に $719^{2021}$ を計算するわけにいきませんよね。（これは、なんと5774桁の数になります…！）

今回は、そんな “累乗の余り” を求める問題について扱いたいと思います。

このあと、そのような問題を解く際に心強い存在となる定理を紹介します。

具体的な２問題を通して、問題を解くときに不安を抱えたまま闇雲に突き進むのではなく、「この方針で解けるのだ」という保証を与えてくれる定理の頼もしさを感じていただければと思います。

はじめに
1. 問題解決の方針と心強い定理の存在
2. 本記事で解決したい２問題
フェルマーの小定理について
定理の一般化（オイラーの定理）
この２定理を用いて問題を解く
1. 問題A
2. 問題B
まとめ

はじめに

問題解決の方針と心強い定理の存在

累乗の余りを求める問題を考えてゆく際に、二項定理を用いて解いても良いのですが、便利なのは高校数学の数学Aで発展的内容として扱われる「合同式」です。

この記事は、合同式の基本的な計算に関する知識が身に付いていることを前提として書かれています。

合同式についてはこちらの記事「合同式（mod）の成り立ち　〜well-definedの意味を考える〜」をご覧ください。

さて、本記事では、累乗の余りを求める問題に臨む際に有効な「フェルマーの小定理」と、その一般化である「オイラーの定理」を高校数学の知識を用いて証明してゆきたいと思います。

これらは共に、累乗の余りの数列から周期性を見出だし、問題を解く際に我々の心強い味方となるのです。

本記事で解決したい２問題

本記事では、以下のふたつの問に答えます。

$719^{2021}$ を $13$ で割った余りを求めよ。
$719^{2021}$ を $100$ で割った余りを求めよ。

数学の問題は、一度は自分の頭で考えることを習慣付けるようにしましょう。

その方が、その後の解説の理解も深まりますし、より印象に残るはずです。

フェルマーの小定理について

累乗の余りに関する考察

$719^{2021}$ など、極めて大きな累乗の数を扱う前に、扱いやすい数で累乗の余りについて観察しましょう。

ここで、$7$ を底とした累乗からなる数列
\begin{align*}
7^1, 7^2, 7^3, 7^4, 7^5, 7^6, \cdots
\end{align*}を考えます。

これらを $5$ で割った余りからなる新しい数列を考えてみましょう。

$5$ を法とすると
\begin{align*}
7^1&=7\equiv 2,\\
7^2&\equiv 2^2=4,\\
7^3&\equiv 2^3=8\equiv 3,\\
7^4&=7\times7^3\equiv 2\times3=6\equiv 1,\\
7^5&=7\times7^4\equiv 2\times1=2,\\
7^6&=7^2\times7^4\equiv 4\times1=4,\\
&\vdots
\end{align*}となります。

これより、新しく得られた余りからなる数列は
\begin{align*}
2, 4, 3, 1, 2, 4, 3, 1, 2, 4, 3, 1, \cdots
\end{align*}という繰り返しの周期を持ちます。

この周期を利用すれば、第 $2021$ 項である $7^{2021}$ を $5$ で割った余りも $2$ であるとすぐにわかるので、大きな収穫です。

この周期を生んでいたのは
$$
7^4\equiv 1 \pmod 5
$$という合同でした。

これにより、余りの数列は第 $4$ 項でリセットされ、周期を生むのです。

一般的に、累乗 $a^m$ を $n$ で割った余りを考えたいとき
$$
a^l\equiv 1 \pmod n
$$なる正の整数 $l$ さえ見つけられれば、余りからなる数列は周期 $l$ を持ち、問題を楽に解くことができるのです。

以下、「この正の整数 $l$ を求めること」がテーマとなります。

定理の主張とは

そのような周期 $l$ を求める方法として「フェルマーの小定理」と呼ばれる定理があります。

主張は以下の通りです。

$p$ を素数とし、$a$ を $p$ と互いに素な正の整数とする。このとき、
$$
a^{p-1}\equiv 1\pmod p
$$が成り立つ。

$a$ の累乗を互いに素な素数 $p$ で割ると、余りは周期 $p-1$ を持つということです。

その周期の存在を保証するのが、このフェルマーの小定理です。

具体例を通して理解しよう

考察で見た数列を思い出すと、$7$ と素数 $5$ は互いに素であるので、定理の主張
$$
7^{5-1}=7^4\equiv 1 \pmod 5
$$が確かに成り立っていましたね。

また、他の例として、$10$ と素数 $13$ は互いに素であるので、定理より
$$
10^{12}=10^{13-1}\equiv 1\pmod {13}
$$が成り立ちます。

これより、周期 $l=12$ が得られましたが、実際のところは $10^6\equiv 1\pmod {13}$ が成り立つので周期は $l=6$ とすることができます。

このように、フェルマーの小定理から求めた周期 $l=p-1$ は最小であるとは限らず、最小の周期 $l$ は $p-1$ の正の約数の中に存在します。

問題を解く際は周期 $l$ が小さい方が便利ですから、いきなり $l=p-1$ とするのではなく、$p-1$ の正の約数を小さい順に $l$ に当てはめて計算してゆくと良いでしょう。

「多項定理」を用いた定理の証明

証明は高校数学の数学IIで習う多項定理を用います。

誘導をつければ、良い演習になるのではないでしょうか。

– – – – – 証明 – – – – –

$p$ を素数とし、$a$ を $p$ と互いに素である正の整数とする。

このとき、$x_1, x_2, \cdots, x_a$ に関する多項式
\begin{align*}
(x_1+x_2+\cdots+x_a)^p-({x_1}^p+{x_2}^p+\cdots+{x_a}^p)\tag{1}
\end{align*}の一般項は、多項定理より $k_1+k_2+\cdots+k_a=p$ なる正の整数 $k_1, k_2, \cdots, k_a$ を用いて
$$
\frac{p!}{k_1!k_2!\cdots k_a!}{x_1}^{k_1}{x_2}^{k_2}\cdots{x_a}^{k_a}
$$と書くことができる。

ここで、一般項の係数は $p$ の倍数である。

実際、係数を $c$ とおくと $\dfrac{p!}{k_1!k_2!\cdots k_a!}=c$ より $p!=ck_1!k_2!\cdots k_a!$ となる。

今、左辺は $p$ の倍数であるので右辺も $p$ の倍数である。

よって、$c, k_1!, k_2!, \cdots, k_a!$ のうち少なくともひとつは $p$ の倍数である。

一方、$k_1<p$、$k_2<p$、$\cdots$、$k_a<p$ であるので、$k_1!, k_2!, \cdots, k_a!$ はいずれも $p$ の倍数ではない。

故に、残りの係数 $c$ は $p$ の倍数でなければならない。

さて、多項式 (1) に $x_1=x_2=\cdots=x_a=1$ を代入すると、
\begin{align*}
a^p-a
&=(1+1+\cdots+1)^p-(1^p+1^p+\cdots+1^p)\\
&=(\mbox{一般項の係数の和})
\end{align*}となる。

一般項の係数が全て $p$ の倍数であることから左辺の $a^p-a$ は $p$ の倍数である。

すなわち、$a(a^{p-1}-1)=a^p-a$ は $p$ の倍数であって、かつ、$a$ は $p$ の倍数ではなかったので、$a^{p-1}-1$ が $p$ の倍数となる。

すなわち
\begin{align*}
a^{p-1}\equiv1\pmod p
\end{align*}を得る。

– – – – – 証明終 – – – – –

定理の一般化（オイラーの定理）

定理の主張とは

フェルマーの小定理は周期 $l$ を見つけるために有効でしたが “素数 $p$ で割った余り” にしか適用できませんでした。

そこで、これを一般化しましょう。

素数 $p$ に対して、$p-1$ というのは「$p$ と互いに素な $p$ 以下の正の整数の個数」になっていますね。

そこで、正の整数 $n$ に対して、「$n$ と互いに素な $n$ 以下の正の整数の個数」を与える関数 $\varphi(n)$ 考えます。

これをオイラーのファイ関数といいます。

このとき、フェルマーの小定理の一般化である「オイラーの定理」が成り立ちます。

その主張は以下の通りです。

$n$ を正の整数、$a$ を $n$ と互いに素である正の整数とする。このとき、
$$
a^{\varphi(n)}\equiv1\pmod n
$$が成り立つ。

$a$ の累乗を互いに素な正の整数 $n$ で割ると、余りは周期 $\varphi(n)$ を持つということです。

素数でない数で割るときにも周期の存在を保証するのが、このオイラーの定理です。

こちらも具体例で理解しよう

例えば、$a=10$、$n=81$ としてみましょう。

まず、$10$ と $81$ は互いに素ですね。

次に、$81=3^4$ と互いに素でない整数は $3$ の倍数であって、$81$ 以下のものは $27$ 個なので
$$
\varphi(81)=81-27=54
$$となります。

よって、
$$
10^{54}\equiv1\pmod {81}
$$が成り立ちます。

ここで、フェルマーの小定理のときと同様に、周期 $l$ は $54$ の正の約数 $1,2,3,6,9,18,27,54$ の中から探すと最小のものが見つかります。

$81$ を法とすると
\begin{align*}
10^1&=10\\
10^2&=100\equiv 19\\
10^3&=10^2\times10\equiv 19\times10=190\equiv 28\\
10^6&=(10^3)^2\equiv28^2\equiv 784\equiv 55\\
10^9&=10^3\times10^6\equiv 28\times55\equiv 1540\equiv 1
\end{align*}より $l=9$ とできますね。

「総乗」が鍵となる定理の証明

証明も高校数学の範囲で可能ですから、示しておこうと思います。

– – – – – 証明 – – – – –

$n$ を正の整数、$a$ を $n$ と互いに素である正の整数とする。

ここで、$n$ と互いに素な $n$ 以下の正の整数の集合を
$$
R=\{r_1, r_2, \cdots, r_{\varphi(n)}\}
$$とおく。

また、この $R$ の各要素に $a$ をかけた整数の集合を
$$
S=\{ar_1, ar_2, \cdots, ar_{\varphi(n)}\}
$$とおく。

このとき、集合 $S$ の要素は、$n$ を法とすれば集合 $R$ の要素を並び替えただけである。

実際、$a$ は $n$ と互いに素なので $S$ の各要素も $n$ と互いに素である。

また、$ar_i\equiv ar_j\pmod n$ ならば $r_i\equiv r_j\pmod n$ であるので、$S$ の各要素も $n$ を法として互いに異なる。

これより、$R$ と $S$ それぞれの要素の総乗は合同である。

よって、前者を $P=r_1r_2\cdots r_{\varphi(n)}$ とおけば
\begin{align*}
P
&=r_1r_2\cdots r_{\varphi(n)}\\
&\equiv(ar_1)(ar_2)\cdots(ar_{\varphi(n)})\pmod n\\
&=a^{\varphi(n)}P
\end{align*}が成り立つ。

今、$P$ も $n$ と互いに素であるので
$$
1\equiv a^{\varphi(n)}\pmod n
$$を得る。

– – – – – 証明終 – – – – –

この２定理を用いて問題を解く

さて、最初に述べておいた問題

$719^{2021}$ を $13$ で割った余りを求めよ。
$719^{2021}$ を $100$ で割った余りを求めよ。

を “大学入試のように” 解いてゆきましょう。

フェルマーの小定理やオイラーの定理は強力ですし、上記で見たように高校数学の範囲で証明可能ですが、入試や定期テストでそのまま解答に使うことはお勧めできません。

それは、標準的な教科書で証明される内容ではないからです。（記述中に上記のような証明を書きさえすれば、もちろん用いて構いません。）

しかし、数学IIIで不定形の極限の検算にロピタルの定理が有効なように、解答に記さなくとも方針の決定には使って構いません。

以下、解答中の心の中の声を “【$\cdots$】” で括って書きますね。

問題A

【法になる $13$ は素数で、$719$ と互いに素だからフェルマーの小定理が使えるな。】

【定理より $719^{12}$ は $1$ に合同だ。$12$ の正の約数を攻めるぞ。】

$13$ を法として $719$ の累乗を計算してゆくと
\begin{align*}
719^1&=719\equiv 4,\\
719^2&\equiv 4^2=16\equiv 3,\\
719^3&=719\times719^2\equiv 4\times3=12\equiv -1,\\
&\mbox{【-1 は 2 乗したら 1 になる！】}\\
719^6&=(719^3)^2\equiv (-1)^2=1
\end{align*}となる。

【余りは周期 $6$ を持つから、$2021$ を $6$ で割ろう】

ここで、$2021=6\times336+5$ であるので
\begin{align*}
719^{2021}
&=(719^6)^{336}\times719^5\\
&\equiv 1^{336}\times719^2\times719^3\pmod {13}\\
&\equiv 1\times3\times(-1)\pmod {13}\\
&=-3\\
&\equiv 10\pmod {13}
\end{align*}となる。

よって、求める余りは $10$ である。

問題B

【法になる $100$ は素数ではないが $719$ と互いに素だからオイラーの定理を使えるな。】

【$100$ と互いに素な数は $2$ または $5$ の倍数なので $\varphi(100)=100-(50+20-10)=40$ となる。】

【定理より $719^{40}$ は $1$ に合同だ。$40$ の正の約数を攻めるぞ。】

$100$ を法として $719$ の累乗を計算してゆくと
\begin{align*}
719^1&=719\equiv 19,\\
719^2&\equiv 19^2=361\equiv 61,\\
719^4&=(719^2)^2\equiv 61^2=3721\equiv 21,\\
&\mbox{【19 と 21 をかけたら 400-1 になる！】}\\
719^5&=719\times 719^4\equiv 19\times 21=399\equiv -1,\\
&\mbox{【-1 は 2 乗したら 1 になる！】}\\
719^{10}&=(719^5)^2\equiv (-1)^2=1
\end{align*}となる。

【余りは周期 $10$ を持つから、$2021$ を $10$ で割ろう】

ここで、$2021=10\times202+1$ であるので
\begin{align*}
719^{2021}
&=(719^{10})^{202}\times719\\
&\equiv 1^{202}\times19\pmod {100}\\
&=19
\end{align*}となる。

よって、求める余りは $19$ である。

（冒頭で述べた、「 $719^{2021}$ の下二桁を求めよ。」の答えは「$19$」ですね。）