今回は初等整数論の面白い話題の 1 つである Fermat の小定理を中心に、周辺の話題を紹介していきます。
0. はじめに
整数論はとても楽しいです。最近では大学受験においても整数論の出題が目立つようになりましたし、計算機科学においても整数論の知見を根底に使っているものが多々あります。整数論はパズルのような楽しさがあるだけでなく、暗号理論など誤り訂正符号など、実用上も重要なものになっています。
Fermat の小定理はそんな初等整数論の中核を成すもので、その証明方法も、使い方も、とても興味深いです。本記事では Fermat の小定理を中心として、周辺話題を整理してみます。
1. Fermat の小定理とは
初等整数論の華とも言うべき楽しい定理です。
$p$ を素数、$a$ を $p$ の倍数でない任意の整数としたとき、
$$a^{p-1} \equiv 1 \pmod{p}$$
が成立する。
ちょっと確かめてみると $p = 7$ として
- $1^6 = 1 \equiv 1 \pmod{7}$
- $2^6 = 64 \equiv 1 \pmod{7}$
- $3^6 = 729 \equiv 1 \pmod{7}$
- $4^6 \equiv (-3)^6 = 3^6 \equiv 1 \pmod{7}$
- $5^6 \equiv (-2)^6 = 2^6 \equiv 1 \pmod{7}$
- $6^6 \equiv (-1)^6 = 1^6 \equiv 1 \pmod{7}$
となって確かに成立しています。
2. Fermat の小定理の証明方針
具体例として $p = 7$ で考えてみます。
唐突ですが、掛け算九九ならぬ、掛け算六六を考えます。ただし、各マスの値を $7$ で割った余りで示します。
| 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 3 | 4 | 5 | 6 |
| 2 | 2 | 4 | 6 | 1 | 3 | 5 |
| 3 | 3 | 6 | 2 | 5 | 1 | 4 |
| 4 | 4 | 1 | 5 | 2 | 6 | 3 |
| 5 | 5 | 3 | 1 | 6 | 4 | 2 |
| 6 | 6 | 5 | 4 | 3 | 2 | 1 |
これを見てわかることは、どの行を見ても「$1, 2, 3, 4, 5, 6$」の並び替えになっています。例えば $3$ の行を見ると ${\rm mod}. 7$ において
- $3 × 1 \equiv 3$
- $3 × 2 \equiv 6$
- $3 × 3 \equiv 2$
- $3 × 4 \equiv 5$
- $3 × 5 \equiv 1$
- $3 × 6 \equiv 4$
となっています。実はこの性質は一般の素数 $p$ について、$1 × 1$ から $(p-1) × (p-1)$ までの掛け算表を書いても成立します。この性質は後で示すとして、まずはこの性質を用いて Fermat の小定理を導きます。
上記の性質から、$(3×1, 3×2, 3×3, 3×4, 3×5, 3×6)$ と $(1, 2, 3, 4, 5, 6)$ とは ${\rm mod}. 7$ では並び替えを除いて等しいことになります。よってこれらを掛け合わせても等しくて、
$(3×1)(3×2)(3×3)(3×4)(3×5)(3×6) ≡ 6! \pmod 7$
⇔ $(6!)3^6 ≡ 6! \pmod 7$
となります。$6!$ と $7$ は互いに素なので両辺を $6!$ で割ることができて、
$3^6 ≡ 1 \pmod 7$
が導かれました。これはフェルマーの小定理の $p = 7$, $a = 3$ の場合ですが、一般の場合でも
- $p$ を任意の素数、$a$ を $p$ で割り切れない任意の整数とする
- $(a, 2a, 3a, ..., (p-1)a)$ と $(1, 2, 3, ..., p-1)$ とは ${\rm mod}. p$ において、並び替えを除いて等しい
- よって、$(p-1)!a^{p-1} ≡ (p-1)!$ なので、$a^{p-1} ≡ 1$ が従う
という流れで証明できます。
3. 証明の残り: 「逆元」の存在
証明の残っている部分は
$p$ を任意の素数、$a$ を $p$ で割り切れない任意の整数とする。
$(a, 2a, 3a, ..., (p-1)a)$ と $(1, 2, 3, ..., p-1)$ とは ${\rm mod}. p$ において、並び替えを除いて等しい
です。比較的簡単な議論で証明できてしまいます。
【証明】
$x, y$ を $1 \le x, y \le p-1$, $x \neq y$ を満たす整数とするとき、$xa$ と $ya$ とが ${\rm mod}. p$ において互いに異なることを示します。
仮に $xa \equiv ya \pmod p$ となり得ると仮定すると、$a(x-y) \equiv 0 \pmod p$ となり、$a$ と $p$ が互いに素であることから
$x - y \equiv 0 \pmod p$
となります。$1 \le x, y \le p-1$ であることから $x = y$ でなければならず矛盾します。
よって、$a, 2a, 3a, ..., (p-1)a$ を $p$ で割ったあまりは、どの 2 つも互いに相異なることがわかりました。$a, 2a, 3a, ..., (p-1)a$ を $p$ で割ったあまりはそれぞれ $0, 1, 2, ..., p-1$ のいずれかになりますが、どの 2 つも互いに相異なることから、これらがちょうど $1$ 回ずつ登場することがわかります。
(証明終)
とてもシンプルな短い議論で証明できました。この性質は以下の重要な事実を表しています。この事実は、$a, 2a, 3a, ..., (p-1)a$ を $p$ で割ったあまりに $1, 2, 3, \dots, p-1$ が 1 回ずつ登場することから自然に従います。
$p$ を素数とし、$a$ を $p$ で割り切れない整数とする。このとき
$$ax \equiv 1 \pmod{p}$$
を満たすような $x$ は $\bmod{p}$ において一意に存在する
このような $x$ のことを「${\rm mod}. p$ における $a$ の逆元」と呼びます。逆元が存在することは、${\rm mod}. p$ の世界において $a ÷ b$ といった割り算ができることを意味しています。その話題について詳しくは
を読んでいただけたらと思います。
4. Fermat の小定理の応用例
Fermat の小定理を用いてできることについて、紹介していきます。
4-1: 逆元を計算する
面白いことに、Fermat の小定理の証明のために登場した「逆元」を、Fermat の小定理によって計算することができます。定理の式を少し変形すると
$a × a^{p-2} \equiv 1 \pmod{p}$
となります。これは、$a^{p-2}$ が $a$ の逆元であることを意味しています。つまり、$a^{p-2} \pmod{p}$ を計算することで $a$ の逆元を求めることができます。
なお逆元を計算する他の方法として拡張 Euclid の互除法を用いた方法があります。詳しくはこの記事を読んでいただけたらと思います。
4-2. 「3 の 100 乗を 19 で割ったあまり」を手計算する
このネタは tsujimotter さんの
です。とても面白い記事なので是非読んでみてください。また、本節の内容は「手計算」を前提としています。コンピュータで「3 の 100 乗を 19 で割ったあまり」を計算しようと思ったら、素直に 100 回掛け算するか、二分累乗法を用いるのがよいです。
さて、Fermat の小定理が主張しているのは
$1, 3, 3^2, 3^3, 3^4, \dots$ を $19$ で割ったあまりは $18$ 個ごとに周期している
ということです。つまり
$$3^{18} \equiv 1 \pmod{19}$$
であることから、
- $3^{0} \equiv 1$
- $3^{1} \equiv 3$
- $3^{2} \equiv 9$
- $3^{3} \equiv 8$
- $3^{4} \equiv 5$
- $\dots$
- $3^{18} \equiv 1$
- $3^{19} \equiv 3$
- $3^{20} \equiv 9$
- $3^{21} \equiv 8$
- $3^{22} \equiv 5$
- $\dots$
- $3^{36} \equiv 1$
- $3^{37} \equiv 3$
- $3^{38} \equiv 9$
- $3^{39} \equiv 8$
- $3^{40} \equiv 5$
という風になっています。これを利用すると、$100 = 18 × 5 + 10$ であることから、$3^{100}$ は以下のように求められます。
$$3^{100} \equiv 3^{10} \pmod{19}$$
が成立するので、$3^{10} \pmod{19}$ が計算できればよいです。これを計算すると $16$ になります。
4-3. レプユニット数
$111111111111111111111111$
のように $1$ が連続している整数をレプユニット数と呼びます。比較的手軽に整数論的考察が楽しめる話題なのでたくさん解説記事があります:
- レプユニット数 (高校数学の美しい物語さん)
- 11/11はレピュニットの日 (tsujimotter さん)
- 1111…1という数（レピュニット）の素因数分解を納得する (もっちょさん)
レプユニット数について、以下の面白い性質が知られています。
$p$ を $2$ と $5$ 以外の素数とするとき、あるレプユニット数が存在して $p$ で割り切れる
つまり、$1, 11, 111, 1111, \dots$ といったレプユニット数を順に素因数分解していって、登場する素数を全部掻き集めたとき、$2$ と $5$ 以外はすべて揃うことになります。証明は簡単で、$k$ 桁のレプユニット数が
$$\frac{10^{k} - 1}{9}$$
と表されることを利用します。$2$ と $5$ 以外の素数 $p$ は $10$ と互いに素なため、Fermat の小定理より
$$10^{p-1} \equiv 1 \pmod{p}$$
が成立します。これは $10^{p-1} - 1$ が $p$ で割り切れることを意味しています。$p$ が $3$ 以外の素数のときは $p$ と $9$ が互いに素であるため、$\frac{10^{p-1} - 1}{9}$ は $p$ で割り切れます。$p = 3$ のときは例えば $111$ が $3$ で割り切れます。以上で示せました。
4-4. mod. p における多項式の解の個数
この節の内容は少し難しくなります。
以下の問題を考えてみます。この問題は実は
で出題されている問題で、答えを求めるプログラムを書いて提出することでジャッジできます。
$p$ を素数とする。
整数係数の $n$ 次多項式 $f(x) = a_n x^{n} + a_{n-1} x^{n-1} + \dots + a_0$ が与えられる。$f(z)$ が $p$ の倍数となるような $z (0 \le z \le p-1)$ の個数を求めよ。
($0 \le n \le 100$, $2 \le p \le 10^9$)
シンプルで心がそそられる問題ですね！
さて、高校数学でお馴染みの「剰余の定理」を思い出します。$f(x)$ を $x-z$ で割ったあまりを $r$ として以下のようにします。
$$f(x) = (x-z)g(x) + r$$
そうすると $f(z) \equiv 0 \pmod{p}$ であることは、$r \equiv 0 \pmod{p}$ であること、つまり $f(x) \equiv (x-z)g(x) \pmod{p}$ であることと同値であることがわかります。これは ${\rm mod}. p$ の意味で、$f(x)$ が $x-z$ で割り切れることを意味しています。
よって、
- $z$ が解のとき、${\rm mod}. p$ の意味で $f(x)$ は $x-z$ で割り切れる
- $z$ が解でないとき、${\rm mod}. p$ の意味で $f(x)$ は $x-z$ で割り切れない
という関係性になっているため、$f(x)$ と $x(x-1)(x-2)\dots(x-(p-1))$ との「多項式の意味での最大公約数」を求めれば、それが $(x-z_1)(x-z_2)\dots(x-z_k)$ となったとき、解は $z_1, z_2, \dots, z_k$ になることがわかります。したがって基本的には、$f(x)$ と $x(x-1)(x-2)\dots(x-(p-1))$ との最大公約数をなす多項式を求めて、その次数が答えになります。
さて、この計算を実行するためのプログラムを書こうと思うと、$p$ は $10^9$ 程度の大きさになることもあるためとても間に合いません。ここで Fermat の小定理を用います。実は
$$x(x-1)(x-2)\dots(x-(p-1)) \equiv x^p - x \pmod{p}$$
が成り立つのでこれを示します。Fermat の小定理は「任意の整数 $a$ に対して $a^p \equiv a \pmod{p}$ が成立する」と言い換えることができるのですが、これは
- $x \equiv 0, 1, 2, \dots p-1$ が $x^p - x \equiv 0$ の解である
ということを意味しています。つまり、$x^p - x$ は $x(x-1)(x-2)\dots(x-(p-1))$ で割り切れるのです。しかるに $x^p - x$ も $x(x-1)(x-2)\dots(x-(p-1))$ も次数が $p$ で等しく、最高次の係数も $1$ で等しいため、
$$x(x-1)(x-2)\dots(x-(p-1)) \equiv x^p - x \pmod{p}$$
であることが確定します。
以上より、$f(x)$ と $x^p - x$ の多項式の意味での最大公約数を求めればいいことが確定しました。多項式に対しても Euclid の互除法がそのまま適用できます。
しかしそのまま計算しては、$p$ が巨大なので無理です。そこで Euclid の互除法の最初のステップだけ工夫します。つまり、
- $x^p - x$ を $f(x)$ で割ったあまりを求める
という部分を工夫します。これは $x^p - x \pmod{f(x)}$ が計算できればよいということですが、これは繰り返し二乗法によって効率的に計算できます。
少々長い議論になりましたが、以下のリンク先のコードで正解を取ることができました。注意点として、$f(x)$ は ${\rm mod}. p$ においては最高次係数が $0$ になるとは限らないのできちんとフォローする必要がありますし、そもそも $f(x) \equiv 0$ となることもあってその場合の答えは $p$ となります。
4-5. その他の問題
競技プログラミングで過去に出題された Fermat の小定理に関係する問題たちを挙げます。少し難しめの問題が多いです。
- AOJ 2610 Fast Division (レプユニット数を題材にした手頃な問題です)
- AOJ 2720 Identity Function (この問題の原案担当でした、整数論的考察を総動員します)
- SRM 449 DIV1 Hard StairsColoring (Fermat の小定理から、カタラン数を 1000000122 で割ったあまりを求める問題に帰着します)
- Codeforces 460 DIV2 E - Congruence Equation (少し難しめですが面白いです、中国剰余定理も使います)
- Tenka1 2017 F - ModularPowerEquation!! (かなり難しいですが面白いです)
5. おわりに
初等整数論の華である Fermat の小定理について特集しました。証明方法が整数論における重要な性質に基づいているだけでけでなく、使い道も色々ある面白い定理です。
最後に Fermat の小定理に関係する発展的トピックをいくつか紹介して締めたいと思います。
Euler の定理
Fermat の小定理は、法 $p$ が素数の場合の定理でした。これを合成数の場合に拡張したのが以下の Euler の定理です。$\phi(m)$ は Euler のファイ関数と呼ばれているもので、$1$ 以上 $m$ 以下の整数のうち $m$ と互いに素なものの個数を表しています。
$m$ を正の整数、$a$ を $m$ と互いに素な整数とする。
$$a^{\phi(m)} \equiv 1 \pmod{m}$$
が成立する。
証明は Fermat の小定理をほんの少し修正するだけでできます。
原始根
上の「$3$ の $100$ 乗を $19$ で割ったあまりを計算する」に述べたことを一般化すると
$1, a, a^2, \dots$ を $p$ で割ったあまりは $p-1$ 個ごとに周期的になる
となりますが、実はもっと短い周期になることもあります。例えば ${\rm mod}. 19$ で $4$ のべき乗を考えると
- $4^0 \equiv 1$
- $4^1 \equiv 4$
- $4^2 \equiv 16$
- $4^3 \equiv 7$
- $4^4 \equiv 9$
- $4^5 \equiv 17$
- $4^6 \equiv 11$
- $4^7 \equiv 6$
- $4^8 \equiv 5$
- $4^9 \equiv 1$
となって、周期が $9$ であることがわかります ($18$ 個ごとに周期していること自体は正しいです)。この周期のことを位数と呼びます。
そうすると自然な問題意識として、「位数が $p-1$ になっているものはあるか？」というのが生まれます。実は任意の素数 $p$ に対して、位数 $p-1$ の元が存在することが知られており、原始根と呼びます。原始根を $r$ とすると、
$1, r, r^2, \dots, r^{p-2}$ を $p$ で割ったあまりは $1, 2, \dots, p-1$ がちょうど 1 回ずつ登場する
という面白い性質が成り立っています。この性質から、$p$ で割り切れない整数 $a$ に対して、指数 ($r$ の何乗か) を定義できることがわかります。この指数を用いると、初等整数論の様々な面白い定理を示すことができます。
また原始根の重要な応用例として、高速フーリエ変換 (FFT) における数値誤差をなくすための技術として知られる高速剰余変換 (NTT) があります。NTT も整数論の実応用例として面白いものだと思います。NTT 系列に勤めていることもあって結構好きなアルゴリズムなので、近いうちに NTT に関する記事も書きたいです。