フェルマー商 - tsujimotterのノートブック

今日は整数論の面白概念の一つであるフェルマー商を紹介したいと思います。

まず、フェルマーの小定理という、合同式を考える上で大変有用な定理から話を始めます。

定理（フェルマーの小定理）

$a$ を $p$ で割り切れない任意の整数とする。このとき

$a^{p-1} \equiv 1 \pmod{p} \tag{1}$

が成り立つ。

つまり、この定理は $p$ と互いに素な $a$ について、 $a^{p-1} - 1$ が必ず $p$ で割り切れると言っているわけですね。

$\bmod{p}$ の剰余も十分面白いのですが、今回はさらに話を進めて $\bmod{p^2}$ の合同式を考えてみたいと思います。

これは、整数 $a^{p-1}$ を $p$ 進展開すると自然に出てくる発想です。

$a^{p-1}$ を

$a^{p-1} = q_0 + q_1 p + q_2 p^2 + q_3 p^3 + \cdots + q_n p^n \tag{2}$

と表せたとしましょう。フェルマーの小定理により

$a^{p-1} \equiv 1 \pmod{p}$

ということなので、式 $(2)$ において $q_0 \equiv 1 \pmod{p}$ であることがわかったことになります。

次に、 $q_0 = 1$ を代入した上で、式 $(2)$ で $\bmod{p^2}$ すると

$a^{p-1} \equiv 1 + q_1 p \pmod{p^2} \tag{3}$

となります。 $q_2$ についての情報が分かれば、 $a^{p-1}$ についてのより多くの情報を獲得したことになりますね。

このあとも同様に $\bmod{p^3}, \bmod{p^4}, \ldots$ として $q_3, q_4, \ldots$ を計算していけば、最終的に $a^{p-1}$ について完全に理解できたことになるわけです。その取っ掛かりとして $\bmod{p^2}$ の情報が欲しいわけです。

とはいえ、 $\bmod{p^2}$ の合同式は $\bmod{p}$ と比べると圧倒的に難しいので、何かしら手がかりが得られれば良しと考えましょう。

式 $(3)$ を言いかえると

$\displaystyle a^{p-1} - 1 \equiv q_2 p \pmod{p^2}$

ということになります。フェルマーの小定理により $a^{p-1} - 1$ は $p$ で割り切れますので、両辺 $p$ で割ると

$\displaystyle \frac{a^{p-1} - 1}{p} \equiv q_2 \pmod{p} \tag{4}$

となります。

要するに式 $(4)$ の左辺の $\bmod{p}$ についての情報が知りたいというわけですね。この左辺のことをフェルマー商と言います。

フェルマー商についての合同式を紹介したいというのが今日のテーマなのですが、結論に行く前にちょっと実験してみましょうか。

$p = 5$ のときを考えてみましょう。太字の数がフェルマー商（ $\bmod{p}$ ）です。

$\begin{align} 1^{4} &\equiv 1 + {\bf 0}\times 5 \pmod{5^2} \\ 2^{4} &\equiv 1 + {\bf 3}\times 5 \pmod{5^2} \\ 3^{4} &\equiv 1 + {\bf 1}\times 5 \pmod{5^2} \\ 4^{4} &\equiv 1 + {\bf 1}\times 5 \pmod{5^2} \\ 6^{4} &\equiv 1 + {\bf 4}\times 5 \pmod{5^2} \\ 7^{4} &\equiv 1 + {\bf 0}\times 5 \pmod{5^2} \\ 8^{4} &\equiv 1 + {\bf 4}\times 5 \pmod{5^2} \\ 9^{4} &\equiv 1 + {\bf 2}\times 5 \pmod{5^2} \\ 11^{4} &\equiv 1 + {\bf 3}\times 5 \pmod{5^2} \\ 12^{4} &\equiv 1 + {\bf 2}\times 5 \pmod{5^2} \\ 13^{4} &\equiv 1 + {\bf 2}\times 5 \pmod{5^2} \\ 14^{4} &\equiv 1 + {\bf 3}\times 5 \pmod{5^2} \\ 16^{4} &\equiv 1 + {\bf 2}\times 5 \pmod{5^2} \\ 17^{4} &\equiv 1 + {\bf 4}\times 5 \pmod{5^2} \\ 18^{4} &\equiv 1 + {\bf 0}\times 5 \pmod{5^2} \\ 19^{4} &\equiv 1 + {\bf 4}\times 5 \pmod{5^2} \\ 21^{4} &\equiv 1 + {\bf 1}\times 5 \pmod{5^2} \\ 22^{4} &\equiv 1 + {\bf 1}\times 5 \pmod{5^2} \\ 23^{4} &\equiv 1 + {\bf 3}\times 5 \pmod{5^2} \\ 24^{4} &\equiv 1 + {\bf 0}\times 5 \pmod{5^2} \end{align}$

この数に何か法則は見いだせるでしょうか。少なくとも、 $\bmod{p}$ のフェルマーの小定理のように、同じ数が出続けるというような法則はなさそうですね。

他の $p$ でも考えてみたいのですが、後の法則に関連して $a = 2$ に固定して考えたいと思います。

$\begin{align} 2^{2} &\equiv 1 + {\bf 1}\times 3 \pmod{3^2} \\ 2^{4} &\equiv 1 + {\bf 3}\times 5 \pmod{5^2} \\ 2^{6} &\equiv 1 + {\bf 2}\times 7 \pmod{7^2} \\ 2^{10} &\equiv 1 + {\bf 5}\times 11 \pmod{11^2} \\ 2^{12} &\equiv 1 + {\bf 3}\times 13 \pmod{13^2} \\ 2^{16} &\equiv 1 + {\bf 13}\times 17 \pmod{17^2} \\ 2^{18} &\equiv 1 + {\bf 3}\times 19 \pmod{19^2} \\ 2^{22} &\equiv 1 + {\bf 17}\times 23 \pmod{23^2} \\ 2^{28} &\equiv 1 + {\bf 1}\times 29 \pmod{29^2} \\ 2^{30} &\equiv 1 + {\bf 6}\times 31 \pmod{31^2} \\ 2^{36} &\equiv 1 + {\bf 1}\times 37 \pmod{37^2} \\ 2^{40} &\equiv 1 + {\bf 23}\times 41 \pmod{41^2} \\ 2^{42} &\equiv 1 + {\bf 25}\times 43 \pmod{43^2} \\ 2^{46} &\equiv 1 + {\bf 44}\times 47 \pmod{47^2} \\ 2^{52} &\equiv 1 + {\bf 36}\times 53 \pmod{53^2} \\ 2^{58} &\equiv 1 + {\bf 8}\times 59 \pmod{59^2} \\ 2^{60} &\equiv 1 + {\bf 36}\times 61 \pmod{61^2} \\ 2^{66} &\equiv 1 + {\bf 10}\times 67 \pmod{67^2} \\ 2^{70} &\equiv 1 + {\bf 2}\times 71 \pmod{71^2} \\ 2^{72} &\equiv 1 + {\bf 56}\times 73 \pmod{73^2} \\ 2^{78} &\equiv 1 + {\bf 19}\times 79 \pmod{79^2} \\ 2^{82} &\equiv 1 + {\bf 48}\times 83 \pmod{83^2} \\ 2^{88} &\equiv 1 + {\bf 6}\times 89 \pmod{89^2} \\ 2^{96} &\equiv 1 + {\bf 57}\times 97 \pmod{97^2} \end{align}$

少し本題とは外れますが、今回の話がテイラー展開と微分係数の関係に似ていると思った方もいるかもしれません。

実際、関数 $f(x)$ のテイラー展開を

$f(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots$

のように表すと、 $x = 0$ として $f(0) = a_0$ が得られます。これは $\bmod{x}$ を取ったことになります。

また、 $\bmod{x^2}$ とると

$f(x) \equiv a_0 + a_1 x \pmod{x^2}$

となり、1次の係数 $a_1$ が出てくるわけですね。

というわけで、フェルマー商は微分係数にちょうど対応するような概念になっています。

アイゼンシュタインの発見した合同式

それでは、本題の合同式を紹介します。アイゼンシュタインが発見したフェルマー商の $\bmod{p}$ の合同式です。

定理（アイゼンシュタイン, 1850年）

$p$ を奇素数とすると、次が成り立つ：

$\displaystyle \frac{2^{p-1} - 1}{p} \equiv -\frac{1}{2} \sum_{k=1}^{\frac{p-1}{2}} \frac{1}{k} \pmod{p} \tag{5}$

ちょっと複雑に見えるかもしれませんが、右辺の和は

$\displaystyle 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{\frac{p-3}{2}} + \frac{1}{\frac{p-1}{2}}$

という形の和に $-\frac{1}{2}$ を掛けたものになっています。

ここで

$\displaystyle H_n = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n-1} + \frac{1}{n}$

という形の和を調和数といいます。調和数を使うと、式 $(5)$ は

$\displaystyle \frac{2^{p-1} - 1}{p} \equiv -\frac{1}{2}H_{\frac{p-1}{2}} \pmod{p} \tag{6}$

のように簡潔に表せますね。

式 $(3)$ の表し方でいうと

$\displaystyle 2^{p-1} \equiv 1 + \left(-\frac{1}{2}H_{\frac{p-1}{2}}\right)p \pmod{p^2} \tag{7}$

と見ることもできます。 $p$ の1次の係数が調和数によって表せるわけですね。

証明に行く前に、軽く実験してみましょう。 $p = 5$ のときを考えます。 $\frac{5-1}{2} = 2$ なので、 $2$ 項の和を考えれば良いですね。

$\displaystyle H_{2} = \frac{1}{1} + \frac{1}{2} = \frac{3}{2}$

したがって

$\displaystyle -\frac{1}{2}H_2 = -\frac{3}{4} \equiv -3 \times 4 \equiv 3 \pmod{5}$

が得られます。最後の１つ前の合同式では $4^{-1} \equiv 4 \pmod{5}$ であることを使いました。

そんなわけで、アイゼンシュタインの定理によって、 $a = 2$ のフェルマー商が　

$\displaystyle \frac{2^{4} - 1}{5} \equiv 3 \pmod{5}$

と求まったわけですが、たしかにこれは左辺を素朴に計算した結果と一致していますね！面白いです！

証明

証明の方針としては、 $2^{p}$ を二項展開によって表すことです。二項展開

$\displaystyle (x+y)^{p} = \sum_{k=0}^{p} \binom{p}{k} x^k y^{p-k}$

に対して、 $x = 1, \; y = 1$ を代入すると

$\displaystyle 2^{p} = \sum_{k=0}^{p} \binom{p}{k} \tag{8}$

が得られます。これを使うわけですね。

また、二項係数を考える上で、補助的に

$\binom{p}{k} \equiv 0 \pmod{p}$ （ただし、 $1 \leq k \leq p-1$ ）
$\binom{p-1}{k-1} \equiv (-1)^{k-1} \pmod{p}$ （ただし、 $1 \leq k \leq p$ ）

という２つの合同式を使うことになります。これらを先に証明しておきましょう。

（1. の証明）
二項係数の定義より

$\displaystyle \binom{p}{k} = \frac{p!}{k! (p-k)!}$

と表せる。ここで、 $1 \leq k \leq p-1$ であれば $k < p$ かつ $p-k < p$ より分母の素因子に $p$ は含まれない。

したがって、分子の $p$ は約分されないので、 $\binom{p}{k}$ は $p$ で割り切れる。

（1. の証明終わり）

（2. の証明）
数学的帰納法により証明する。

$k = 1$ のとき、 $\binom{p-1}{k-1} = \binom{p-1}{0} = 1 = (-1)^{k-1}$ より成立。

$k = j$ （ただし $1 \leq j \leq p-1$ ）で成立すると仮定すると

$\displaystyle \begin{align} \binom{p-1}{j} &= \binom{p}{j} - \binom{p-1}{j-1} \\ &\equiv 0 - (-1)^{j-1} \;\;\;\;\;\; (\because \; \binom{p}{j} \equiv 0 \pmod{p} \;\text{より}) \\ &\equiv (-1)^{(j+1)-1} \pmod{p} \end{align}$

より、 $k = j+1$ で成立。したがって、 $1 \leq k \leq p$ において成立。

（2. の証明終わり）

これで準備はできましたので、本題の定理を証明したいと思います。

$\displaystyle \begin{align} -2 \cdot \frac{2^{p-1} - 1}{p} &= -\frac{1}{p}(2^{p} - 2) \\ &= - \frac{1}{p} \left( \sum_{k=0}^{p}\binom{p}{k} - \binom{p}{0} - \binom{p}{p} \right) \;\;\;\; (\because 2^p = \sum_{k=0}^{p}\binom{p}{k}, \;\;\; \binom{p}{0} = \binom{p}{p} = 1) \\ &= - \frac{1}{p} \sum_{k=1}^{p-1}\binom{p}{k} \\ &= - \frac{1}{p} \sum_{k=1}^{p-1}\binom{p-1}{k-1}\frac{p}{k} \\ &= - \sum_{k=1}^{p-1}\binom{p-1}{k-1}\frac{1}{k} \\ &\equiv - \sum_{k=1}^{p-1}\frac{(-1)^{k-1}}{k} \pmod{p} \;\;\;\; (\because \;\; \text{2.} \;\;\; \binom{p-1}{k-1} \equiv (-1)^{k-1} \;\text{より}) \end{align}$

ここで中間的な結果として、次が得られましたのでまとめておきましょう：

$p$ を奇素数とすると、次が成り立つ：

$\displaystyle \frac{2^{p-1} - 1}{p} \equiv \frac{1}{2} \sum_{k=1}^{p-1} \frac{(-1)^{k-1}}{k} \pmod{p} \tag{9}$

さらに計算を進めます。

$\displaystyle \begin{align} -2\cdot \frac{2^{p-1} - 1}{p} &\equiv -\sum_{k=1}^{p-1} \frac{(-1)^{k-1}}{k} \pmod{p} \\ &\equiv -\frac{1}{1} + \frac{1}{2} - \frac{1}{3} + \frac{1}{4} - \cdots - \frac{1}{p-4} + \frac{1}{p-3} - \frac{1}{p-2} + \frac{1}{p-1} \\ &\equiv \left(-\frac{1}{1} - \frac{1}{3} - \cdots - \frac{1}{p-4} - \frac{1}{p-2} \right) + \left(\frac{1}{2} + \frac{1}{4} + \cdots + \frac{1}{p-3} + \frac{1}{p-1} \right) \\ &\equiv \left(-\frac{1}{-(p-1)} - \frac{1}{-(p-3)} - \cdots - \frac{1}{-4} - \frac{1}{-2} \right) + \left(\frac{1}{2} + \frac{1}{4} + \cdots + \frac{1}{p-3} + \frac{1}{p-1} \right) \;\;\;\; (\because \;\; -\frac{1}{k} \equiv -\frac{1}{-(p-k)} \pmod{p}) \\ &\equiv 2\left(\frac{1}{2} + \frac{1}{4} + \cdots + \frac{1}{p-3} + \frac{1}{p-1} \right) \\ &\equiv \frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{\frac{p-3}{2}} + \frac{1}{\frac{p-1}{2}} \\ &\equiv H_{\frac{p-1}{2}} \pmod{p} \end{align}$

したがって

$\displaystyle \frac{2^{p-1} - 1}{p} \equiv -\frac{1}{2}H_{\frac{p-1}{2}} \pmod{p}$

が得られました。

（証明終わり）

おわりに

今回は、フェルマーの小定理から議論を進めて $\bmod{p^2}$ について考えるために、フェルマー商 $\frac{a^{p-1} - 1}{p}$ を導入しました。

特に $a = 2$ については、フェルマー商は

$\displaystyle \frac{2^{p-1} - 1}{p} \equiv -\frac{1}{2}H_{\frac{p-1}{2}} \pmod{p}$

のように表せるということを示しました。

今回は $a = 2$ の場合だけを考えましたが、軽く調べた感じだとそれ以外の $a$ についてもたくさん研究されているそうです。
en.wikipedia.org

冒頭で「 $\bmod{p}$ の法則を見つけたら $\bmod{p^2}$ に持ち上げたくなる」という話をしました。フェルマーの小定理の他にも、たとえばウィルソンの定理 $(p-1)! \equiv -1 \pmod{p}$ からウィルソン商

$\displaystyle \frac{(p-1)! + 1}{p}$

なるものを考えることもあるそうです。

こういう $\bmod{p^2}$ の整数論って、一般的にまとまっていたりするんでしょうかね？
（ご存知の方がいましたら教えてください。）

最後に

$\displaystyle 2^{p-1} \equiv 1 \pmod{p^2}$

であるような $p$ をヴィーフェリッヒ素数といいます。

言い換えると、 $a = 2$ のフェルマー商

$\displaystyle \frac{2^{p-1} - 1}{p} \equiv -\frac{1}{2}H_{\frac{p-1}{2}} \pmod{p}$

が $\bmod{p}$ で $0$ に合同ということですね。

このような素数 $p$ はとってもレアな存在で、現在までに $p = 1093, \; 3511$ の２つしか見つかっていません。

先ほどの定理でいうと

$H_{\frac{1093 - 1}{2}} \equiv 0 \pmod{1093}$

$H_{\frac{3511 - 1}{2}} \equiv 0 \pmod{3511}$

ということです。本当でしょうか？

実際

$H_{\frac{1093 - 1}{2}} = \frac{58327169195545941383347269002790689820229384641642768338355107518411013717082039849876331022039596791259181422003204873753982978244145450039845022952316236093973811645476026866179629164713110029001540649832994996089328344095966696383}{8476862005724850113659597338367410220575592600412485689185331933232255382054144161073264497394204493428675601907752653849678050252696808363363990033125782944856180857041322818409073319768378501437911493533858161095580895759575411200}$

とのことですが、分子は $1093$ で割り切れます！（確かに成り立っている！！）

また

$H_{\frac{3511-1}{2}} = \frac{17796679960896240169918301499907199433285071122957961870365738652082131197155553282178669821800795149434586594508445780823592976860389415200623594470172902416970311388947078105892034242523907137863613919791898685055054338297956981194270384615096104960445787821377820970062408344224498055014668415985646683257133980775487016266298632140663124934234924949559757583002780602881611743656844906966761753099270789284165036271899063493922005899957017096290520152096140525281457014706982886374341865770045090628520816999053114559131713116210538244784052252495639408766937254741587154372321685611460607855455077204671223097510005090908523799953712510790976995194012769740586887171332318150935651886882760090841913440007952602441151399064704993818206619918906386705696132074327}{2211392745371291314525103230956308663508367257312309050073286772104572597324824721891482750671005201532662818172049482908968702133695720001616287000195588183388378947317478122856893270025495773931863846675176259708913987045059734449681116222186881824016624499354559151627201957186468884005654225975596777467917597616852042782399224885219695399113204156777886871036396126430197619789177607347706977665696286350876637267540580505091147365634425696178475715133823480237041538650134630894761207175716998197735448471802434841443182698733349888658665768635269912862742738243852614271811197458664951813334159059719930360355146561259927183992522634955346035478217274346653666228130765008859305687474659799583927967360284276914370224250508648136657861861412683064941892480000}$

となりますが、やはり分子は $3511$ で割り切れます！

ところで、最初の $p = 5$ の実験結果で

$\begin{align} 1^{4} &\equiv 1 + {\bf 0}\times 5 \pmod{5^2} \\ 7^{4} &\equiv 1 + {\bf 0}\times 5 \pmod{5^2} \\ 18^{4} &\equiv 1 + {\bf 0}\times 5 \pmod{5^2} \\ 24^{4} &\equiv 1 + {\bf 0}\times 5 \pmod{5^2} \end{align}$

となっていたのが気になった方もいるかもしれません。

これは $a^{p-1} \equiv 1 \pmod{p^2}$ が成り立つ $(a, p)$ の組ということになりますが、このような $p$ を基数 $a$ の一般化ヴィーフェリッヒ素数というそうです。 $p = 5$ は基数 $a = 1, 7, 18, 24$ の一般化ヴィーフェリッヒ素数ということですね。