tsujimotterのノートブック

日曜数学者 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}

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


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

  1. \binom{p}{k} \equiv 0 \pmod{p}（ただし、 1 \leq k \leq p-1）
  2. \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 の一般化ヴィーフェリッヒ素数ということですね。


そんな感じで色々と広がりがありそうなテーマですが、興味を持っていただけたら幸いです。

それでは今日はこの辺で！


参考文献

アイゼンシュタインの定理の証明については、こちらの回答を参考にさせていただきました。
math.stackexchange.com