インテジャーズ

読者です 読者をやめる 読者になる 読者になる

インテジャーズ

数、特に整数に関する記事。

2015の階乗を10の502乗で割った数の一の位は?

この記事は「日曜数学Advent Calendar」の19番目の記事として寄稿しています:
www.adventar.org

前回はToshiki Takahashi氏による「情報理論の物理学的基礎」でした。
情報理論のための物理基礎 | Advent Calendar 2015 | DIY Mathematics |

私自身は10番目の記事として
integers.hatenablog.com
を既に寄稿しましたので、今回が2回目ということになります。当ブログは色々な整数の性質を紹介することを目的としており、1回目の記事では5882353を取り上げました。

今回は特定の数を取り上げる普段のスタンスからは逸脱しますが、日曜数学者tsujimotter氏が日曜数学Advent Calendarの8番目の記事として寄稿した
tsujimotter.hatenablog.com
が大変素晴らしい記事でしたので、それにインスパイアされた話を書きたいと思います(当初書く予定であったFibonacci平方数については既に投稿しました)。

tsujimotter氏が取り上げたのは

3^{100}19で割ったあまりは?

という問題に4通りの解答を与えるというもの。この問題自体は次のニコニコ動画にインスパイアされたそうです:
www.nicovideo.jp

tsujimotter氏の魅力的な文章により、多くの人がこの記事を楽しく読まれたことと思います。私もその一人であり、「3^{100}というとてつもなく大きい数を19で割った余りなんてどうやって求めるんだ!?」という、この手の問題に初めて出会ったときの絶望感と、その鮮やかな解法を知ったときの感動を思い出しました。

2, 3名、tsujimotter氏の記事を受けて新たに記事を書いた方がおられるようで、私も何か書きたくなりました。しかしながら、「3^{100}19で割ったあまりは?」という問題自体は一度勉強すればとてつもなく簡単なので、流石にこれ以上掘り下げようがない(笑)。

というわけで似たような感じの、しかしもう少しだけ難しい、別の問題を取り上げることにします。

問1 2015!を10進法表記で表したときに末尾に並ぶ0の個数を求めよ。
問2 問1で求めた個数をnとするとき、\displaystyle \frac{2015!}{10^n}の一の位を求めよ。

是非、解答を見ずに一度チャレンジしてみてください*1

「階乗」については以前、記事を書きました:
integers.hatenablog.com

なお、この問題は1999年の日本数学オリンピック予選の問題です。「3^{100}19で割ったあまりは?」を見て、この問題を思い出したというわけです。ただし、2015年なので数値は変えてみました。

解法1 テトラちゃん方式

テトラちゃんは数学ガールに登場する人気キャラクタです。地道な努力による解法を「テトラちゃん方式」と呼ぶそうです(tsujimotter氏命名)。今回の問題も当然、テトラちゃん方式で解くことは可能です。つまり、まず2015!を計算しましょう:

\begin{align}&2015!=\\
&1153695229068993700894415022682284743714582512084074130079487479927\\
&6862236497204005872364016688936735464494550719160093175479895774351\\
&3837822117214103257597178352496809046401016158900678045364681566811\\
&3569941958614528489744484421593172909006192767010870834818197333523\\
&7463182584517923960820352196337046977879865504052390815830708853411\\
&7801484433855443444487042528902839239231790743561914216146989169154\\
&5420967622836555152811095137401703664660333211337325672145638641240\\
&5492536736662429244698886840754406167110922210303304137505782272359\\
&4036196033865171763374390726646777310282738602283513734275899017778\\
&0184121666402119482477956093764657347372928903690612605364052409945\\
&7628788539996739424757518211293550002884788146802990941946816316658\\
&5385676604191793245461306459744620556663412515965044392704592326045\\
&9102681775732561648621501123538285360427306770576047863246076726929\\
&0326859748006626809016420096345535167255926693077263753206853596436\\
&9583260182630760354047773119597543028263098960543550834379248505786\\
&8910074832811432350573986324327485260352990931567486429326229624927\\
&4385413502934363839165932041070639049124613806341133706659204304303\\
&1074291681070501140681297466528539712476824528301965568209652208608\\
&1574694979387344276536057445362844850361820015608926519904520347028\\
&8671212639530039345884327078626996903884237395682362994851847813244\\
&1910527466322494035533117081578339008141728379987378372881672519289\\
&6355815040667008012497677054750731990079451982258848589256393946784\\
&3018961354651106529406588757178862262147442677961212530145575676105\\
&9251094275143171883797010823429916515460843493960160960110160860579\\
&6206226577377115369055986130508923196997289043257556060892321602839\\
&9156207530875796122781795868554151537284275699183329120971163993268\\
&6072834828150397570870388140189810341016533589875096884681310830599\\
&7434638291380419299096611557532326140921852784528648038974413077871\\
&5068597043072863636132215342306401227110726395195538545777180802307\\
&5482395227886022310589431236880352262556687372127453914780776569572\\
&1805385889191858077953939888551940296316287470199164903542124441321\\
&6166961906055631903114147012393421265729785418045171672279298509652\\
&5757902480609221762198572573058190002221633075717869548795437094970\\
&7764913391062120328089655733173084918124851900344386098837354022312\\
&0598517790676293165980382306062621756728187853676583051048757607501\\
&3996995861285708290056455032649931627305227675495428335496869464884\\
&4649844806184489328464952913223686021754615290267705526011301222774\\
&4150706420873641375690532768807714429802065499841778139174382483965\\
&9911704716178738641984897669228629596372656069025807682846364162615\\
&3169408067967441732857200253899752768095192271439782014450931444203\\
&9822158651517414373752346666113565176927181239573344433450060260286\\
&5792771802500526576732815349371811314111144860392015610341061617516\\
&1105875366619012315512247636160588609783982897195000183664690052808\\
&1867955195103363077729495033352263848458946942967985745002233123711\\
&5301124609488321142874672263257421781716665322501964424361446933993\\
&7779378419734497474121498202707044639730922553928904351664266283770\\
&4421588114654532031372161841990359942102032574844186945384278676804\\
&6927882286618931773591599224917454457585360600810492825392667626032\\
&0530208671479619691449350450912734663284877831105490532582748627620\\
&5643863806562197248297574178952169461616662097985917079590294353657\\
&1435755092159396784645685933081451183131665407788817947527674394249\\
&1888137898470046918320226786819730986284617348004264063099869102042\\
&9013967802020335402478709247716692055350802489114320285321470899362\\
&0085115680821304240024314639591092709134829775035778833828805252312\\
&8244771194080412507189912869301473220509509596395729256608032658521\\
&7946425831197503184962568189843891212868900163127724444195713352381\\
&9247279561859931162389171172435705890749561081822677493064981332445\\
&0699078021983885227997172457081694639920652318658909592071214483022\\
&8419490705381216703975663608645430421417137457041786904704555639115\\
&4948032248715904212754063690862344075520119896423882165244977461910\\
&2116493165118731591234469371719987127228913244267746065790058079330\\
&1321715349598352866604969934556290113041577929798997188904669320917\\
&1010925517568610057535879620928422320445810963494343019789081518958\\
&5812174380696879620872946534601735129194891116328598931936997073426\\
&0728607118172222840722235619593499850462080763762256525116369770108\\
&5714188893626673620218072794255858446246104889039332869960865322054\\
&8634164824343093427773790142158993164004401802644320484904592027832\\ &7146544867045485435242233786875754337885927437738134362789129694469\\
&3271551458471819177561818311929515601615964801165960997618245365134\\
&2746217467366671430374512821526487209780500594693598563677088025541\\
&0365469297200868750271115466502906241190500817232974262139186260554\\
&2589795284722973916646310153705288427741652455864810511078751359442\\
&9538271842458933083337250910989020270956442192422604673832771410825\\
&5521699173511019381198908084949271512335560062005647564586759562402\\
&9745021213128601203305484044029796755845690570160524639799149430835\\
&4566237790806665950210976277082472498236238473092771767766340304689\\
&4645760258776091389090247461778065430457119611043641813379592726345\\
&4015405616593506627324002018139111083638171202344852451923276483349\\
&836800825214200204493396442400276135978851672506786801254\color{red}{4}000000000\\
&0000000000000000000000000000000000000000000000000000000000000000000\\
&0000000000000000000000000000000000000000000000000000000000000000000\\
&0000000000000000000000000000000000000000000000000000000000000000000\\
&0000000000000000000000000000000000000000000000000000000000000000000\\
&0000000000000000000000000000000000000000000000000000000000000000000\\
&0000000000000000000000000000000000000000000000000000000000000000000\\
&0000000000000000000000000000000000000000000000000000000000000000000\\
&000000000000000000000000\end{align}

はい、計算できました。0を数えれば502個です。0が終わるところが赤字で示した通り4です。めでたし、めでたし!!

解法2 もう少し頭を使った解き方

テトラちゃん方式は数学の研究においては極めて大事ですが、それだけでは問題の本質(数学的な構造)を理解したことにはならないことが多いです。また、数をもっと大きくすれば通用しなくなります。それにこの問題では下の方の桁の情報のみが要求されているので、全てを計算するのは不要な情報が多すぎます。もう少し賢い方法でこの問題を解きましょう。tsujimotter氏の解説における方法2~4を知れば、「100という数の大きさは問題の難しさに影響しない」ことが分かります。実際、以下の解法も2015をどんな自然数に変更しても通用します

問1の解答

2015!10^nで割り切れるような最大のnを求める問題です。ところで、10=2\times 5なので、「2015!の素因数分解における2の指数と5の指数を求めればよい」です。ところが、少し考えれば、2015!の素因数分解に現れる2の指数は5の指数より大きいことがわかります(25より小さいので、2015までに5より頻繁に2が素因数として出現する)。結局、2015!の素因数分解に現れる5の指数を求めればそれが所望のnであることがわかりました。

それでは2015!=1\times 2\times 3\times \cdots \times 2014 \times 20155がどれだけ出現するかをカウントしましょう。
まず、\displaystyle \frac{2015}{5}=403なので、5の倍数が2015までに403個あることがわかります。
(5\times 1 = 5, 5\times 2 = 10, \dots, 5\times 403 = 2015)

これでは、数え漏れがあります。というのも、例えば255の倍数としてカウントされていますが、25=5^25の指数は2なので、もう一回カウントしなければなりません。

というわけで、2015以下の5^2=25の倍数の個数をカウントします。\displaystyle \frac{2015}{25} = 80.6なので、80個あることがわかります。
(5^2\times 1=25, 5^2\times 2 = 50, \dots, 5^2\times 80 = 2000)

次は同じように数え漏らした5^3の倍数をカウントします。\displaystyle \frac{2015}{125} = 16.12なので、16個。
(5^3\times 1 = 125, 5^3\times 2 = 250, \dots, 5^3\times 16 = 2000

5^4の倍数の個数。\displaystyle \frac{2015}{625} = 3.224より、3個。
(5^4\times 1 = 625, 5^4\times 2 = 1250, 5^4\times 3 = 1875)

5^5=3125 > 2015なので、これで全てをカウントできました。というわけで、2015!の素因数分解に現れる5の指数は403+80+16+3=502であることがわかりました。 よって、答えはn=502です(2015!を全部計算しなくても、末尾に0502個並ぶということがこんなに簡単にわかる!)。

問2の解答

考え方-各素数毎に考察する
(考え方の個人的な解説なので、Step1に跳んでも数学的には問題ありません。)
問2は\displaystyle \frac{2015!}{10^{502}}\bmod{10}で決定する問題です。しかし、いきなりこれを求めるのは難しいため、2つのStepに分けて考察します。整数論では「問題を各素数の問題に分割して、まずそれを解決し、後に統合する」という考え方が有効な場合がしばしばあります。素数はもともと「数の素」です。整数は素数から出来ています。なので、素数のレベルで問題を考察すれば整数の問題は解けるはずであると考えることが出来ます*2。合同式の問題でもこの考え方は有効です(cf. 中国式剰余定理。また、「\bmod素数」限定で成り立つ法則は多い)。というわけで、本来は\bmod{10}で解かなければならないですが、\bmod{2}\bmod{5}で何と合同かが分かれば\bmod{10}で何と合同かも分かります。ところで、「素数である」という観点だけでみると25も違いはないのですが、大きさを比べると差があります。\bmod{2}で考えるというのは要は偶奇を見るという話です。なので、\bmod{5}で考えれば後は簡単という構造になっています。というわけで\displaystyle \frac{2015!}{10^{502}}\bmod{5}で決定することを最初の目標とします。

\displaystyle \frac{2015!}{10^{502}}という整数を調べるということは2015!から10^{502}を削った数を調べるということです。しかし、実際には1から2015の間に10の累乗が規則正しく現れて10^{502}が出来上がるわけではありません。25はそれぞれが自由奔放に現れて、全体として10^{502}が作られるのです。というわけで、ここでも素数2と素数5を分割して考察する方が議論しやすいです。つまり、Step1では\displaystyle \frac{2015!}{5^{502}}\bmod{5}で決定することに専念します。その後に残った2^{502}を処理しなければなりませんが、この部分はtsujimotter氏のブログで培った方法で瞬殺できます(Step2)。

Step1
\displaystyle \frac{2015!}{5^{502}}\bmod{5}で何と合同であるかを決定します。2015!から5^{502}を消滅させるために、1から2015の整数を次のような5つのグループに分けます*3

グループ① 5と互いに素な数
1, 2, 3, 4, 6, 7, 8, 9, 11, \dots, 2013, 2014

グループ② 5^1で丁度割り切れる数*4
5=5\times 1, 10=5\times 2, 15=5\times 3, 20=5\times 4, 30=5\times 6, \dots,
2010=5\times 402, 2015=5\times 403

グループ③ 5^2で丁度割り切れる数
25=5^2\times 1, 50=5^2\times 2 75=5^2\times 3, 100 = 5^2\times 4, 150=5^2\times 6, \dots,
1950=5^2\times 78, 1975 = 5^2\times 79

グループ④ 5^3で丁度割り切れる数
125=5^3\times 1, 250=5^3\times 2 375=5^3\times 3, 500 = 5^3\times 4, 650=5^2\times 6, \dots,
1750 = 5^3\times 14, 2000 = 5^3\times 16

グループ⑤ 5^4で丁度割り切れる数
625=5^4\times 1, 1250=5^4\times 2, 1875=5^4\times 3

各グループの数の個数は次のようになっています:
グループ① 2015-403=1612個 (全体-5の倍数の個数)
グループ② 403-80=323個 (5の倍数の個数-5^2の倍数の個数。以下、同様)
グループ③ 80-16=64
グループ④ 16-3=13
グループ⑤ 3

5と互いに素であるような自然数nに対して、「1からnまでの5と互いに素な整数全部の積」を\Pi_nと定義します。数式で書けば、\Pi_n \displaystyle:= \prod_{k \in \{ l \mid l \in \mathbb{Z}, 1 \leq l \leq n, \ 5 \nmid l \}}kです。

例)

\begin{align}\Pi_1&=1\\
\Pi_2&=1\times 2=2\\
\Pi_3&=1\times 2\times 3 =6\\
\Pi_4&=1\times 2\times 3\times 4=24\\
\Pi_6&=1\times 2\times 3\times 4\times 6=144\\
\Pi_7&=1\times 2\times 3\times 4\times 6\times 7=1008\\
\Pi_8&=1\times 2\times 3\times 4\times 6\times 7\times 8=8064\\
\Pi_9&=1\times 2\times 3\times 4\times 6\times 7\times 8\times 9=72576\end{align}

また、グループ①に所属する数全体の積をA_1, グループ②に所属する数全体の積をA_2、…とA_5まで定めます。このとき、

\begin{align}A_1&=\Pi_{2014}\\
A_2&=5^{323}\Pi_{403}\\
A_3&=5^{2\times 64}\Pi_{79}\\
A_4&=5^{3\times 13}\Pi_{16}\\
A_5&=5^{4\times 3}\Pi_{3}\end{align}

となっていることが分かります。323+2\times 64+3\times 13+4\times 3 = 502なので、

\displaystyle \frac{2015!}{5^{502}}= \Pi_{2014}\Pi_{403}\Pi_{79}\Pi_{16}\Pi_{3}

と考察すべき数が\Pi_nの形の数の積になっていることが分かりました。従って、あとは「\Pi_n\bmod{5}で求める方法を見つける」ことに問題が帰着されました。

nが小さいときは次のようになっています:

\Pi_1 \Pi_2 \Pi_3 \Pi_4 \Pi_6 \Pi_7 \Pi_8 \Pi_9
\bmod{5} 1 2 1 4 4 3 4 1

実は、この表だけで\Pi_n \bmod{5}が全て求められます。というのは、次の補題が成り立つからです:

補題 \ \ \ \ \ \ n \equiv m \equiv \pmod{10} \Longrightarrow \Pi_n \equiv \Pi_m \pmod{5}

証明. \bmod{5}で考えると、

\begin{equation}\begin{split}\Pi_n&=1\times 2\times 3\times 4 \times 6\times 7\times 8\times 9\times 11\times 12\times 13\times 14\times \cdots \times n \\ &=(1\times 2\times 3\times 4) \times (6\times 7\times 8\times 9)\times (11\times 12\times 13\times 14)\times \cdots \times n \\ &\equiv (1\times 2\times 3\times 4)\times (1\times 2\times 3\times 4) \times (1\times 2\times 3\times 4) \times \cdots \pmod{5}\end{split}\end{equation}

(1\times 2\times 3\times 4)の繰り返しになっている。これは24 \equiv -1 \pmod{5}なので、この繰り返し節が2回現れると\equiv 1 \pmod{5}となる。\bmod{10}毎にこの繰り返し節が2回現れるので、\Pi_n \bmod{5}n \bmod{10}で決まる。 Q.E.D.

というわけで、\Pi_n \bmod{5}を知りたければnの一の位(n'とします)に対する\prod_{n'}を表で確認すればよいことがわかりました(なんと簡単なんでしょう!)。

こうして、

\begin{equation}\begin{split}\frac{2015!}{5^{502}}&= \Pi_{2014}\Pi_{403}\Pi_{79}\Pi_{16}\Pi_{3} \equiv \Pi_{4}\Pi_3\Pi_9\Pi_6\Pi_3 \\ &= 4\times 1 \times 1\times 4\times 1 \equiv 1 \pmod{5}\end{split}\end{equation}

が分かりました。

Step2
\displaystyle A:=\frac{2015!}{10^{502}}, B:=\frac{2015!}{5^{502}}としましょう。このとき、2^{502}A=Bが成り立ちます。ここで、次の問題を解きましょう:

2^{502}5で割ったあまりは?

もう皆さんにとっては簡単ですね?答えは2^{502} \equiv 4 \equiv -1 \pmod{5}です。よって、-A\equiv B、すなわち、A \equiv -B \equiv -1 \equiv 4 \pmod{5}が分かりました(Step1よりB\equiv 1\pmod{5})。するとA \equiv 4\pmod{10}またはA \equiv 9\pmod{10}です。ところで、問1の解答でみたように、2015!の素因数の指数は5のそれより2のそれの方が大きいので、Aは偶数であることがわかります。以上により、A \equiv 4\pmod{10}が確定しました。 答えは4。

別の問題

この記事では解答はつけませんが、ここまで読まれた皆さんなら次の問題は難なく解くことができるでしょう:

日本数学オリンピック予選2000年
{}_{40}C_{20}41で割ったあまりは?
日本数学オリンピック予選2001年
1^{2001}+2^{2001}+\cdots 2000^{2001}+2001^{2001}13で割ったあまりは?

さて、tsujimotter氏の記事の素晴らしいところは問題を解くだけではなく、その問題を題材に整数論の法則(Fermatの小定理、Eulerの規準、平方剰余の相互法則など)を解説しているところです。読者の方々の中には「なんで、こんな簡単な問題を解くために平方剰余の相互法則なんていう小難しいことを書いているのだろうか。むしろ、効率が悪いのではないか?」と思った方もおられるでしょう。私が勝手に推察するに、彼はあの問題なんてどうでもよく、「平方剰余の相互法則という極めて美しい公式を人に伝えたかった」のでしょう。いえ、そうに違いありません(違ったらすみません(笑))。

というわけで、問題は簡単でしたが、それを題材にいくつかの法則、公式を紹介したいと思います。

\mathbb{Z}/p\mathbb{Z}は体をなす

上記解法が完全に理解できたかを確認したければ、2015!を他の任意のn!にしても解けるかを色々な具体例で試せばよいです。このとき、一つ問題があります。Step2で2^{502} \equiv -1\pmod{5}となったことが偶然であるということです。そうならない場合でも解けるかをみてみましょう。

例)16!の末尾から数えて初めて0でなくなった数を求める。

解. 16/5=3.2なので、16!の末尾には03つ並ぶことがわかる。\displaystyle A:= \frac{16!}{10^3}, B:=\frac{16!}{5^3}とする。このとき、B = \Pi_{16}\Pi_3 \equiv \Pi_6\Pi_3 \equiv 4 \pmod{5}8A = Bであり、8 \equiv 3 \pmod{5}であるから、3A \equiv 4 \pmod{5}を得る。ここで、両辺を2倍すると6A \equiv 8 \equiv 3\pmod{5}であるが、A \equiv 6A \pmod{5}なので、A \equiv 3 \pmod{5}が分かる。従って、A \equiv 3 \ \text{or} \ 8 \pmod{10}Aは偶数なので、求める数は8であることが分かる。実際、16!=20922789888000である。

2015よりはるかに小さい数を選んだので幾分簡潔に見えます。しかし、「両辺を2倍すると」という部分だけ最初の解法にはなかった工夫です。実際のところ、2の冪乗を5で割ったあまりは1, 2, 3, 4 \equiv \pm 1, \pm 2なので、2\times 3 =6 \equiv 1 \pmod{5}さえ確認できれば2^{\bullet}A\bmod{5}からA\bmod{5}が求まることが分かります。このように上手くいくのは偶然だったのでしょうか?例えば、2の代わりに素数q5の代わりに素数pとしても同じようなことができる保証はあるのでしょうか(p \neq q)?つまり、整数Aに対してある整数mが存在してq^mA\bmod{p}が分かっているときにA\bmod{p}を決定する方法はあるでしょうか?まず、q^mpと互いに素なので、「pと互いに素な整数aに対してaA\bmod{p}が分かっているときにA\bmod{p}を知ることができるか?」という問題に帰着されます。そして、それを解くためには「ab \equiv 1 \pmod{p}なる整数bが存在する」ことを示せばよいです。実際、このようなbが見つかればA \equiv abA \pmod{p}となって、aAb倍したものを\bmod{p}で計算すればよいことが分かります。
話が長くなりましたが、「ab \equiv 1 \pmod{p}なる整数bが存在する」はどんな素数pに対しても正しいことがわかります。つまり、上の解法が上手くいったのはある意味で偶然ではありません。また、素数でなければこのような法則は成り立ちません(例えば3b \equiv 1 \pmod{6}なるbは存在しない)。

定理 pを素数とし、apと互いに素な整数とする。このとき、ab \equiv 1 \pmod{p}なる整数bが存在する。

これを証明するために次の補題を用意します:

xyが互いに素な整数であるとき、sx+ty=1なる整数s, tが存在する。

これはx, yに対するEuclidの互除法を逆に辿ることによって示せます。1037で例を示します(それが証明になっていると言っていいでしょう):

\begin{align}37&=3\times 10+7\\
10&=1\times 7+3\\
7&=2\times 3+1\end{align}

\begin{align}1&=7-2\times 3\\
&=7-2(10-1\times 7)\\ &=3\times 7-2\times 10\\
&=3(37-3\times 10)-2\times 10\\ &=3\times 37-11\times 10\end{align}

こうして、3\times 37 - 11\times 10 = 1、つまりx=37, y=10に対してs=3, t=-11と取れることが分かりました。

今、apは互いに素なので、ab+pc=1となる整数b, cが存在することが補題より分かります。このとき、ab \equiv 1 \pmod{p}なので示したかったことが証明されました。なお、上記定理を代数学の言葉で表現すると「\mathbb{Z}/p\mathbb{Z}は体をなす」となります。

Wilsonの定理

\prod_nn\bmod{10}で決まることを示した際に、1\times 2\times 3\times 4 \equiv -1\pmod{5}が出現しました。実はこれも偶然ではありません。次の定理が成り立ちます:

Wilsonの定理 任意の素数pに対して(p-1)! \equiv -1 \pmod{p}が成り立つ。

証明. 以前紹介した「原始根の存在定理」を用いると瞬殺できます:
integers.hatenablog.com
pを奇素数とし、r\bmod{p}の原始根とする(p=2の場合は自明)。このとき、集合\{1, 2, \dots, p-1\}\{r^0, r^1, r^2, \dots, r^{p-2}\}\bmod{p}でみると一致する。よって、

\begin{equation}\begin{split}(p-1)! &\equiv r^{0+1+2+\cdots +(p-2)} = r^{\frac{1}{2}(p-1)(p-2)}\\ &=(r^{\frac{p-1}{2}})^{p-2}\equiv (-1)^{p-2}=-1 \pmod{p}\end{split}\end{equation}
Q.E.D.

ちなみに、(n-1)!\equiv -1 \pmod{n}が成立することとnが素数であることは同値です。

さて、奇素数pに対して\Pi_n^{(p)}\displaystyle:= \prod_{k \in \{ l \mid l \in \mathbb{Z}, 1 \leq l \leq n, \ p \nmid l \}}kとしましょう(npと素な自然数)。このとき、一般に次の周期性があることがWilsonの定理により分かります。

n \equiv m \pmod{2p} \Longrightarrow \Pi_{n}^{(p)} \equiv \Pi_{m}^{(p)} \pmod{p}

Legendreの公式

問1の解法によりn!の素因数分解に現れる5の指数が求められるようになりました。この方法は当然5以外の素数に対しても適用できます。というわけで次の公式が得られます:

Legendreの公式 \ \ \ \ \ \ \displaystyle \mathrm{ord}_p(n!) = \sum_{m=1}^{\infty}\left[ \frac{n}{p^m} \right] = \sum_{m=1}^{[ \log_pn]}\left[ \frac{n}{p^m} \right] .

[ \ ] はGauss記号です。この公式は広く「Polignacの公式」として知られているのですが、Dicksonの研究によりLegendreの方が先にこの公式を得ていたと指摘されています。これは超有名公式ですが、入試問題でも取り扱われるようです。

京大文系2009
pを素数、nを自然数とするとき、(p^n)!pで何回割れるか?

この年受験した人は1問分時間を短縮できてラッキーですね。さて、Legendreの公式は単純に考えれば「階乗で表される数の素因数分解を求める公式」なので、いかにも公式と呼ぶにふさわしいものです。ところが、意外にも高い応用性を秘めています。その応用の一つを紹介したいと思います。

素数の無限性

Legendreの公式を用いた素数の無限性の証明
素数が有限個であったと仮定する。全ての素数を掛けて出来る整数をPとおく。Legendreの公式により

\displaystyle \mathrm{ord}_p(n!)=\sum_{m=1}^{\infty}\left[ \frac{n}{p^m} \right] \leq \sum_{m=1}^{\infty}\frac{n}{p^m} = \frac{n}{p-1}\leq n

なる評価が得られるので、

\displaystyle n! = \prod_pp^{\mathrm{ord}_p(n!)} \leq \prod_pp^{n} = P^n

が成り立つ。十分大きいnを考えるとn! > P^nであるから矛盾。 Q.E.D.

指数関数よりも階乗関数の方が成長スピードが速いということを利用した上手い証明法と言えます。最後の部分の証明については
integers.hatenablog.com
を参照してください。

この証明法を見ると、明らかに次の定理の証明に拡張できることが分かります。

定理 \ \ \ \displaystyle \sum_p\frac{\log p}{p} = \infty.

和は全ての素数を走ります。
Legendreの公式を用いた上記定理の証明
Legendreの公式により\displaystyle \mathrm{ord}_p(n!)\leq \frac{n}{p-1}なので、

\displaystyle n! \leq \prod_{p\leq n}p^{\frac{n}{p-1}}
を得る。両辺の対数をとれば

\displaystyle \log (n!) \leq \sum_{p\leq n}\frac{n\log p}{p-1} < \sum_{p\leq n}\frac{n\log p}{p}.

\displaystyle \lim_{n \to \infty}\frac{\log (n!)}{n}=\inftyなので、

\displaystyle \lim_{n \to \infty}\sum_{p\leq n}\frac{\log p}{p} = \infty

が従う。 Q.E.D.
最後の極限公式はStirlingの公式のとても弱い場合ですが一応証明しておきましょう: \displaystyle \int_{k-1}^k\log x dx<\log kなので、

\displaystyle n\log n-n+1 \leq \sum_{k=1}^n\log k

を得る。よって、

\displaystyle \log n-1 +\frac{1}{n} \leq \frac{\log (n!)}{n}.

Q.E.D.

歴史的なことを申し上げますと、素数の無限性証明はWhangによって2010年に発表されたものです。これは時代を逆行しており、実際には大昔からLegendreの公式の有効性は認識されていました。ChebyshevがLegendreの公式を用いて、素数定理の弱い版(\displaystyle \pi (x) \asymp \frac{x}{\log x})を証明したのが始まりと言ってよいと思われます。その後、ErdősがBertrandの仮説(n2nの間には必ず素数が存在する)に関する一連の仕事でLegendreの公式を応用しています。これらはどれも素数が無限に存在することよりはるかに強いことを示しています。また、Whangの証明を受けて、上記のように素数に関する和の発散を示しましたが、Legendreの公式からこれが示せることはErdős(1938)、Eckford Cohen(1969)も指摘しています。この和の発散はMertensの第一定理の弱い版ですが、Mertensの定理については別の記事で取り扱いたいと思います。

素数の逆数和

Legendreの公式を用いて\displaystyle \sum_p\frac{\log p}{p}=\inftyを証明しましたが、ついでにもっと強い次の定理を証明しておきましょう(将来の記事のためにも早めに扱っておくのが都合がよいです):

素数の逆数和は発散する。すなわち、\displaystyle \sum_p\frac{1}{p} = \infty

2通りの証明を紹介しますが、キーポイントはともに「square-freeな部分が効いてくる」ことです。

第一証明(by Vanden Eynden). 自然数は「無平方部分\times平方数」と一意的に分解できることが素因数分解の一意性によりわかる。例) 1080 = (2\times 3\times 5) \times 6^2の無平方部分は2\times 3\times 5、平方数部分は6^2です。n以下の自然数の無平方部分に現れる素数はn以下であり、平方数部分に現れる平方数もn以下なので、

\displaystyle \sum_{k=1}^n\frac{1}{k} \leq \prod_{p\leq n}\left( 1+\frac{1}{p} \right)\sum_{k=1}^{[\sqrt{n}]}\frac{1}{k^2}

が成り立つ(右辺を展開すれば分かる)。ところで、

\displaystyle \lim_{n \to \infty}\sum_{k=1}^n\frac{1}{k} = \infty

および

\displaystyle \lim_{n\to \infty}\sum_{k=1}^{[\sqrt{n}]}\frac{1}{k^2}<\infty

であるので(過去の記事
integers.hatenablog.com
integers.hatenablog.com
を参照せよ)、

\displaystyle \lim_{n \to \infty}\prod_{p\leq n}\left( 1+\frac{1}{p} \right) = \infty

が示された。さて、簡単な不等式1+x < e^x \ (x>0)を用いると

\displaystyle \prod_{p\leq n}\left( 1+\frac{1}{p} \right) < \prod_{p \leq n}e^{\frac{1}{p}} = e^{\sum_{p \leq n}\frac{1}{p}}

が分かるので、\displaystyle \lim_{n \to \infty}\sum_{p \leq n}\frac{1}{p} = \inftyが従う。 Q.E.D.

第二証明(by Erdős). p_jj番目の素数とする。素数の逆数和が収束したと仮定する。このとき、\displaystyle \frac{1}{p_{i+1}}+\frac{1}{p_{i+2}}+\cdots < \frac{1}{2}なる番号iがとれる(このようなiを固定する)。集合S(x)S(x):= \{ n \in \mathbb{N} \mid n \leq x, n\text{は}p_i\text{より大きい任意の素数で割り切れない} \}と定義する。N(x) := \# S(x)とする。n \in S(x)n=mk^2と無平方部分mと平方数部分k^2に分ける。このとき、mm=p_1^{e_1}p_2^{e_2}\cdots p_i^{e_i} \ (e_1, \dots, e_i \in \{0, 1\}) と素因数分解されるので、mの候補は高々2^i通りである。一方、k\leq \sqrt{n} \leq \sqrt{x}なので、場合の数をカウントすることによりN(x) \leq 2^i\sqrt{x}が示された。
さて、x以下の自然数であってS(x)の元でないものはp_{i+1}, p_{i+2}, \dotsのうち少なくとも1つで割り切れる。x以下のp_jの倍数は\displaystyle \left[ \frac{x}{p_j} \right] 個あるので、

\displaystyle x-N(x) \leq \left[ \frac{x}{p_{i+1}} \right] + \left[ \frac{x}{p_{i+2}}\right] + \cdots \leq \frac{x}{p_{i+1}}+\frac{x}{p_{i+2}}+\cdots < \frac{x}{2}

を得る(iの取り方に注意)。よって、\displaystyle \frac{x}{2} < N(x) \leq 2^i\sqrt{x}が成り立つ。すなわち、x < 4^{i+1}が成り立つというのである!x \geq 4^{i+1}なるxを考えれば、これは即座に矛盾である。 Q.E.D.

この定理もMertensの第二定理の弱い版です。

明日の日曜数学Advent Clendarはtsunut氏の『食べられる「アレ」の製造シュミレーション(1)』です!「アレ」が何かは現時点では想像しかできないですが、是非食べましょう!!

*1:扱っている数がとても大きくて計算で解くのは大変ですが、うまく考察すればすっきり解けるという点でtsujimotter氏が取り扱った問題に似ていると感じました。解答でみるようにmodulo計算で周期的な部分が現れる点も似ています。

*2:あくまで考え方ですので、統合する部分がとても難しかったり、そもそも出来なかったり、分割しなくてもすんなり解けたりと色々な場合があります。しかしながら、「素数に限定するとシンプルな法則が成り立つ」ということはよくあります。現代整数論では「局所大域原理」という哲学と結びつきます

*3:ここでいうグループは群ではありません。

*4:5では割り切れるが5^2では割り切れない数のこと。グループ③~⑤についても同様。